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

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

 

# 미확인 도착지
import heapq
import sys
input = sys.stdin.readline


def dijkstra(start, arr):
    q = []
    heapq.heappush(q, (0, start))
    visited = [sys.maxsize for _ in range(n+1)]
    visited[start] = 0
    while q:
        dist, node = heapq.heappop(q)
        if visited[node] < dist:
            continue
        for ndist, nnode in arr[node]:
            if visited[nnode] > dist+ndist:
                visited[nnode] = dist+ndist
                heapq.heappush(q, (dist+ndist, nnode))
    return visited


T = int(input())
for _ in range(T):
    n, m, t = map(int, input().split())
    start, x, y = map(int, input().split())
    arr = [[]for _ in range(n+1)]
    for _ in range(m):
        a, b, dist = map(int, input().split())
        arr[a].append((dist, b))
        arr[b].append((dist, a))
    goal = []
    for _ in range(t):
        goal.append(int(input()))

    s = dijkstra(start, arr)
    m1 = dijkstra(x, arr)
    m2 = dijkstra(y, arr)
    result = []
    for k in goal:
        if s[x]+m1[y]+m2[k] == s[k] or s[y]+m2[x]+m1[k] == s[k]:
            result.append(k)
    print(*sorted(result))

 

최단거리, 다익스트라
1. 입력을 받는다. (start : 시작 위치, x : 중간지점, y : 중간지점, goal : 도착지들)
2. start, x, y 에서 출발하는 다익스트라 총 세 번, 해당 결과 리스트 반환
3. goal리스트 요소(k) 중에서 아래 조건에 만족하는 값만 result에 append
    - (start에서 k로 가는 최단거리 == start에서 x와 y를 거치고 k로 가는 최단거리)
    - 조건을 만족하면 start[k]는 x와 y사이의 거리를 지나는 최단거리가 됨
4. result를 정렬해서 요소 출력