이번 문제는 다익스트라 알고리즘을 통해 해결하였다. 그래프는 양방향 인접 리스트로 구현하였고, 보통의 다익스트라 알고리즘과 같이 각 노드까지의 거리를 저장하는 리스트를 최대값으로 채워둔 뒤에 각 노드들에 가는데 필요한 비용을 비교하여 더 작은 비용을 취하도록 하는 방식으로 접근하였다. 건우가 있는 노드를 지나는지의 여부를 판별하는 것에 대하여 고민을 많이 하다가 시작 노드부터 목적지 노드까지의 최소 거리가 시작 노드부터 건우의 노드까지의 최소 거리 + 건우의 노드부터 목적지 노드까지의 최소 거리와 같을 경우 건우를 도와준 것으로 판별하도록 하였다.

• v, e, p를 입력받는다.
• graph를 2차원 리스트로 선언한다.
• e만큼 반복하는 for문을 돌린다.
  -> a, b, c를 입력받는다.
  -> graph[a]에 (b, c)를 넣는다.
  -> graph[b]에 (a, c)를 넣는다.
• 최대값을 저장할 변수 INF를 선언하고 sys.maxsize를 저장해준다.
• dijkstra 함수를 start, end를 인자로 갖도록 하여 선언한다.
  -> 각 노드까지의 거리를 저장할 리스트 dist를 INF v+1개로 채운다.
  -> dist[start]를 0으로 갱신한다.
  -> 다익스트라에 사용할 큐 q를 최소힙으로 선언하고, (0, start)를 넣어준다.
  -> q가 있을동안 반복하는 while문을 돌린다.
  --> q에서 distance, cur을 추출한다.
  --> 만약 distance가 dist[cur]보다 클 경우, 다음 반복으로 넘어간다.
  --> graph[cur]을 순회하는 nxt, dst에 대한 for문을 돌린다.
  ---> nxt_distance를 distance+dst로 저장한다.
  ---> 만약 nxt_distance가 dist[nxt]보다 작을 경우,
  ----> dist[nxt]를 nxt_distance로 갱신한다.
  ----> q에 (nxt_distance, nxt)를 넣는다.
  -> dist[end]를 반환한다.
• 만약 dijkstra(1, v)가 dijkstra(1, p)+dijkstra(p, v)와 같을 경우, SAVE HIM을 출력한다.
• 그 외에는 GOOD BYE를 출력한다.

Code

import sys
import heapq
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))
INF=sys.maxsize
def dijkstra(start, end):
    dist=[INF for _ in range(v+1)]
    dist[start]=0
    q=[]
    heapq.heappush(q, (0, start))
    while q:
        distance, cur=heapq.heappop(q)
        if distance>dist[cur]:
            continue
        for nxt, dst in graph[cur]:
            nxt_distance=distance+dst
            if nxt_distance<dist[nxt]:
                dist[nxt]=nxt_distance
                heapq.heappush(q, (nxt_distance, nxt))
    return dist[end]
if dijkstra(1, v)==dijkstra(1, p)+dijkstra(p, v):
    print('SAVE HIM')
else:
    print('GOOD BYE')