1. 문제 설명

민준이와 마산 그리고 건우

2. 문제 분석

다익스트라 알고리즘을 통해 1번 노드에서 다른 모든 노드에 대한 최단 거리를 구한다. 도착지에서 거꾸로 출발지까지 BFS를 실시하면서 사용한 경로 중 원하는 건우가 위치한 노드가 있는지 확인하자.

3. 나의 풀이

import sys
import heapq
from collections import deque

v, e, p = map(int, sys.stdin.readline().rstrip().split())
nodes= [[] for _ in range(v+1)]
for _ in range(e):
    a, b, c = map(int, sys.stdin.readline().rstrip().split())
    nodes[a].append([b, c])
    nodes[b].append([a, c])
INF = sys.maxsize
def Dijkstra():
    distances = [INF for _ in range(v+1)]
    distances[1] = 0
    pq = []
    heapq.heappush(pq, [0, 1])

    while pq:
        cur_cost, cur_node = heapq.heappop(pq)

        if distances[cur_node] < cur_cost: continue

        for next_node, next_cost in nodes[cur_node]:
            if distances[next_node] > next_cost + cur_cost:
                distances[next_node] = next_cost + cur_cost
                heapq.heappush(pq, [next_cost+cur_cost, next_node])

    return distances

def BFS():
    queue = deque()
    queue.append(v)

    while queue:
        cur_node = queue.popleft()
        if cur_node == p: return True

        for post_node, post_cost in nodes[cur_node]:
            if distances[post_node] + post_cost == distances[cur_node]:
                queue.append(post_node)
    return False

distances = Dijkstra()
if BFS(): print("SAVE HIM")
else: print("GOOD BYE")