BOJ - 18223

백준 문제 링크
민준이와 마산 그리고 건우

❓접근법

1. 다익스트라 알고리즘을 활용했다.
2. 기본 다익스트라 소스코드를 전개한다.
3. 최단경로임을 찾는 법은 출발이 1, 도착이 v, 건우가 p 이므로
   dijkstra(1)[v] == dijkstra(1)[p] + dijkstra(p)[v]를 만족하면
   최단경로이다.

👌🏻코드

import heapq

INF = int(1e9)

v, e, p = map(int, input().split())

graph = [[] for _ in range(v + 1)]

for _ in range(e):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))
    
def dijkstra(start):
    
    distance = [INF] * (v + 1)
    
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    
    while q:
        dist, now = heapq.heappop(q)
        
        if distance[now] < dist:
            continue
            
        for i in graph[now]:
            cost = dist + i[1]
            
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
                
    return distance

if dijkstra(1)[v] == dijkstra(1)[p] + dijkstra(p)[v]:
    print('SAVE HIM')
else:
    print('GOOD BYE')