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

https://www.acmicpc.net/problem/18223

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

정점 1에서 V까지 가는 최단경로 중에 P를 지나는 경로가 존재하면 "SAVE HIM", 존재하지 않으면 "GOOD BYE"를 출력하는 문제이다.

 

최단경로를 찾는 데는 다익스트라 알고리즘을 사용하여 구현하였고, 기존 다익스트라 문제와 다르게 경로를 체크해야 하므로 save 배열을 따로 만들어 경로 중에 P가 있으면 True가 되도록 하였다.

또한 최단 경로가 여러개 있을 수 있기 때문에 현재 업데이트되는 거리가 기존 거리와 같은 경우에도 경로 중에 P가 있다면 save[v]=True가 되도록 조건을 추가했다.

 

처음에는 save[P] = True로 주고 최단 경로를 갱신할때마다 save[v] = save[now_visit] 이렇게 하도록 했는데, 이렇게하면 중간에 save[P]가 False가 되기 때문에 모든 배열이 False가 된다. 따라서 반복문 중간에 if (v==P) 이면 save[v] = True 라는 조건을 추가하였다. 

 

import sys, heapq
sys = sys.stdin.readline
V, E, P = map(int, input().split())
graph = [[] for _ in range(V+1)]
ans = [float('INF')] * (V+1)
save = [False]*(V+1)
#save[P] = True
for _ in range(E):
    a, b, c = map(int, input().split())
    graph[a].append([b,c])
    graph[b].append([a,c])
    
def solve(start):
    ans[start] = 0
    h = []
    heapq.heappush(h, [ans[start], start])
    while(h):
        now_dist, now_visit = heapq.heappop(h)
        if (ans[now_visit] < now_dist):
            continue
        for v, d in graph[now_visit]:
            dist = now_dist + d
            if (dist < ans[v]):
                ans[v] = dist
                heapq.heappush(h, [dist, v])
                if (v==P):
                    save[v] = True
                else: save[v] = save[now_visit]
            elif (dist == ans[v]):
                if (save[now_visit]==True):
                    save[v] = True

solve(1)

if (save[V]==True): print("SAVE HIM")
else: print("GOOD BYE")