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

문제

 

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

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

---

Algorithm

양방향 간선이고, 문제에서 요구하는 것이 건우의 위치를 지나는 path가 최단거리인지 확인하는 문제이다.

양방향 간선이므로, 시작점이 1인 dijkstra알고리즘과 시작점이 4인 dijkstra알고리즘을 돌려서 두개의 path의 값을 비교해 주면 된다.

둘의 값이 같으면 건우의 위치를 지나도 최단거리이므로 SAVE HIM을 출력해주면 되고, 값이 다르면 건우의 위치를 지나지 않는 것이므로 GOOD BYE를 출력해주면 된다.

그래프는 동일하고, 각 정점까지의 거리를 담는 배열을 2개 따로 선언하여 각각 dijkstra알고리즘을 실행해 주면 된다. 

...
distance_nopass = [INF] * (n+1)
distance_pass = [INF] * (n+1)
...
def dijkstra(start,distance):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    ...

배열 2개를 돌려야 하므로 dijkstra 함수에 인자를 넣어주는 것으로 변경하면 된다.

---

 

 

Code

input = __import__('sys').stdin.readline
import sys
import heapq
sys.setrecursionlimit(10**6)

#정점, 간선의 개수 및 건우의 위치
n,m,passpoints= map(int, input().split())
INF = int(1e9)
#그래프는 동일
graph= [[] * (n+1) for _ in range(n+1)]
#시작점이 1인 distance, 시작점이 passpoints인 distance 선언
distance_nopass = [INF] * (n+1)
distance_pass = [INF] * (n+1)

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b,c))
    graph[b].append((a,c))


def dijkstra(start,distance):
    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]))

#알고리즘 실행
dijkstra(1,distance_nopass)
dijkstra(passpoints,distance_pass)

#거리 비교
least_distance = distance_nopass[n]
passpoint_distance = distance_pass[1]+distance_pass[n]

if least_distance == passpoint_distance:
    print("SAVE HIM")
else:
    print("GOOD BYE")