백준 10282 해킹

과정

• 다익스트라
• 단방향이고, b에서 a로 향하는 것에 주의한다.
• 같은 의존성이 여러 번 입력으로 들어오는지, 그렇지 않은지도 생각하기.

import sys
import heapq

tc = int(input())
INF = 1e9

def dijkstra(start, n):
    # init
    dp = [INF] * n
    q = []
    heapq.heappush(q, (0, start))
    dp[start] = 0
    while q:
        time, now = heapq.heappop(q)
        # 이미 처리된 곳
        if dp[now] < time:
            continue
        # q
        for i in graph[now]:
            cost = time + i[1]
            if dp[i[0]] > cost:
                dp[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
    return dp


for _ in range(tc):
    n, d, c = map(int, input().split())

    graph = [[] for _ in range(n)]

    for _ in range(d): # 의존성 반영 (노드, 시간)
        a, b, s = map(int, sys.stdin.readline().split())
        graph[b-1].append((a-1, s))


    res = dijkstra(c-1, n)
    cnt = 0
    time = 0
    for i in res:
        if i != INF:
            cnt += 1
            if time < i:
                time = i
    print(cnt, time)
    ```