[백준] 9370 미확인 도착지 - 파이썬

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

9370번: 미확인 도착지

풀이

다익스트라 알고리즘을 사용했으며 문제에서 목적지까지 최단경로로 이동하는데 주어진 교차로를 무조건 지나야한다.

출발지 - g - h - 목적지 혹은 출발지 - h - g - 목적지가 출발지 - 목적지까지의 최단경로와 동일하다면 교차로를 지나가는것이다. 다만 교차로를 지나가지않는데도 최단경로 값이 같을 수 있지않나 싶다.(입력값이 그렇게 주어진다면..) 다른분들의 풀이를 보니 지나가야하는 교차로에 float 값을 집어넣어서 최단경로에 float값이 더해져있다면 교차로를 지나간걸로 판단하는 풀이을 하시던데 그 풀이가 더 맞지않나 싶다..

# 9370번 미확인 도착지
# 다익스트라 start - h - g - target와 start - g - h - target 경로 계산
import heapq
import sys
INF = sys.maxsize
input = sys.stdin.readline

def dijkstra(start):
    q = []
    distance = [INF] * (n+1)
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        for v, w in graph[now]:
            cost = dist + w
            if distance[v] > cost:
                distance[v] = cost
                heapq.heappush(q, (cost, v))
    return distance

t = int(input())
for _ in range(t):
    n, m, c = map(int, input().split())
    graph = [[] for i in range(n+1)]
    start, g, h = map(int, input().split())
    target = []
    for _ in range(m):
        a, b, d = map(int, input().split())
        graph[a].append((b, d))
        graph[b].append((a, d))
    for _ in range(c):
        target.append(int(input()))
    from_start = dijkstra(start)
    from_g = dijkstra(g)
    from_h = dijkstra(h)
    ans = []

    for t in target:
        if from_start[g] + from_g[h] + from_h[t] == from_start[t] or from_start[h] + from_h[g] + from_g[t] == from_start[t]:
            ans.append(t)

    # 목적지가 오름차순으로 주어지지않기 때문에 직접 오름차순으로 바꾸어준다.
    ans.sort()

    for i in ans:
        print(i, end=' ')
    print()

 

출력결과