악곱 == 악성곱슬

다익스트라

---

이 문제는 최단 경로 문제를 다익스트라를 응용해서 푸는 문제이다.

주어진 입력의 크기가 노드의 개수가 최대 2000, 간선의 개수가 최대 50000 이므로 우선순위 큐를 사용하는 다익스트라의 경우 O(ElogE) or O(ElogV)를 만족하기 때문에 플로이드를 사용하지 못하고, 다익스트라를 사용해야 함을 눈치챌 수 있다.

어떻게 사용할 것인가?

우선 문제를 이해해야 한다.

• 서커스 예술자는 목적지 까지 무조건 최단경로로 이동한다.
• 최단 경로중 지나간 간선이 있다. 이를 통해 목적지 후보들 중 진짜로 갔을법한 목적지 후보를 추려내야 한다.

따라서 출발지를 S, 경유간선의 양 노드를 G, H 라고 하고 도착지를 D라고 해보자.

S → D 까지의 최단 경로와 S → G → H → D가 일치하면 목적지 후보에 부합한다. 이는 최단경로의 optimal substructure에 의해 알 수 있다.

이 성질을 이용하여 S → G, H→ D 라는 최단 경로를 얻어내기 위해 총 2번의 다익스트라 알고리즘을 사용하면 해결할 수 있음을 알 수 있다. (G → H)는 그냥 간선 정보에서 찾아내기

코드는 다음과 같다.

구현

---

import sys
import heapq

def dijkstra(n, start):
    dist = [INF] * (n + 1)
    dist[start] = 0
    heap = []
    heapq.heappush(heap, (0, start))
    while heap:
        cost, cur = heapq.heappop(heap)
        if cost > dist[cur]:
            continue
        for adj_node, adj_cost in adj_lst[cur].items():
            if adj_cost + dist[cur] < dist[adj_node]:
                dist[adj_node] = adj_cost + dist[cur]
                heapq.heappush(heap, (adj_cost + dist[cur], adj_node))
    return dist

def solution(n, start, must_pass1, must_pass2):
    dist_from_start = dijkstra(n, start)
    if dist_from_start[must_pass1] < dist_from_start[must_pass2]:
        near, far = must_pass1, must_pass2
    else:
        near, far = must_pass2, must_pass1
    dist_from_far = dijkstra(n, far)

    result = []
    for target in targets:
        if dist_from_start[target] == (dist_from_start[near] + adj_lst[near][far] + dist_from_far[target]):
            result.append(target)
    result.sort()
    print(' '.join(str(x) for x in result))

if __name__ == "__main__":
    INF = int(1e9)
    test_cases = int(sys.stdin.readline().rstrip())
    for _ in range(test_cases):
        N, M, T = map(int, sys.stdin.readline().rstrip().split())
        S, G, H = map(int, sys.stdin.readline().rstrip().split())
        adj_lst = [dict() for _ in range(N+1)]
        targets = []
        for _ in range(M):
            A, B, D = map(int, sys.stdin.readline().rstrip().split())
            adj_lst[A][B] = D
            adj_lst[B][A] = D
        for _ in range(T):
            targets.append(int(sys.stdin.readline().rstrip()))
        solution(N, S, G, H)