[BOJ] 18223 - 민준이와 마산 그리고 건우 (Python)

 

 

아이디어

 

데이크스트라 알고리즘으로 민준이가 마산으로 가는 최단 경로와 건우를 거쳐 마산으로 가는 최단 경로를 구한다.

 

 

풀이

 

import sys

input = sys.stdin.readline

INF = int(1e8)

def solution():

    def dijkstra(idx):
        D = [INF]*(V+1)
        D[idx] = 0
        queue = [(idx, 0)]
        while queue:
            u, c = queue.pop(0)
            if D[u] < c:
                continue
            for v, _c in graph[u]:
                if D[v] > c+_c:
                    D[v] = c+_c
                    queue.append((v, c+_c))
        return D

    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))
    D1 = dijkstra(1)
    D2 = dijkstra(P)
    if D1[P]+D2[-1] == D1[-1]:
        print('SAVE HIM')
    else:
        print('GOOD BYE')

solution()