[Python] 백준 18223번 민준이와 마산 그리고 건우

문제

18223번: 민준이와 마산 그리고 건우

입력

• 입력의 첫 번째 줄에 정점의 개수 V와 간선의 개수 E, 그리고 건우가 위치한 정점 P가 주어진다. (2 ≤ V  ≤ 5,000, 1 ≤ E ≤ 10,000, 1 ≤ P  ≤ V)
• 두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보 a,b,c가 공백으로 구분되어 주어진다. 이는 a번 정점과 b번 정점 사이의 거리가 c임을 의미한다. (1 ≤ a,b ≤ V, 1 ≤ c  ≤ 10,000)

출력

• 민준이가 찾은 최단 경로 위에 건우가 있다면 "SAVE HIM" 을 아니면 "GOOD BYE" 를 출력한다.

입력 예제

6 7 4
1 2 1
1 3 1
2 3 10
3 4 1
3 5 2
4 5 1
5 6 1

4 3 3
1 2 1
2 3 1
2 4 1

출력 예제

SAVE HIM

GOOD BYE

문제 풀이

• 다익스트라 알고리즘 수행
• v까지 가는 최단경로의 값보다 p를 거쳐 v로 가는 값이 작거나 같다면 save하고 그렇지 않다면 버린다.
• 연산 결과 출력

코드

import heapq
import sys
input = sys.stdin.readline
v,e,p = map(int,input().split())
INF = int(1e9)
distance = [INF] * (v + 1)
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):
    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

# p를 거쳐가는 비용이 최단 경로의 길이보다
# 같거나 작으면, 구해주러 가기.
if dijkstra(1)[v] >= dijkstra(1)[p] + dijkstra(p)[v]:
    print('SAVE HIM')
else:
    print('GOOD BYE')