10282번: 해킹 (그래프, 다익스트라) - Fastcampus

www.acmicpc.net/problem/10282

10282번: 해킹

import sys
import heapq


def dijkstra(N, start):
    qu = []
    heapq.heappush(qu, (0, start))
    dist = [float("inf")] * (N+1)
    dist[start] = 0

    while qu:
        d, node = heapq.heappop(qu)
        if d > dist[node]:
            continue

        for w, e in graph[node]:
            nd = d + w
            if nd < dist[e]:
                dist[e] = nd
                heapq.heappush(qu, (nd, e))
    return dist


T = int(input())
for _ in range(T):
    N, D, C = map(int, input().split())
    graph = [[] for _ in range(N+1)]
    for _ in range(D):
        n1, n2, w = map(int, sys.stdin.readline().split())
        graph[n2].append((w, n1))

    ans = dijkstra(N, C)
    ans = [x for x in ans if x != float("inf")]
    print(len(ans), max(ans))