[백준] 10282번-(Python 파이썬) - Dijkstra

문제링크 : https://www.acmicpc.net/problem/10282

이번 문제도 다익스트라 알고리즘으로 구현해주었다.
a, b, s가 입력이 됐을 때, a가 b를 의존한다는 표현이
b → c 라는 점을 캐치하지 못해 시간이 조금 걸렸었던 문제이다.
다 풀었는데 왜 자꾸 답이 다를까를 고민하고 다시 문제를 읽어보니 해결되었다.

방향성이 있는 그래프를 만들어 준 뒤 다익스트라 알고리즘으로 최단시간을 구해준다.
그 시간 중 가장 큰 값과 컴퓨터 개수를 출력해주면 된다.

import sys
from heapq import heappush, heappop

input = sys.stdin.readline
inf = sys.maxsize

def dijkstra(start, dp, graph):
    heappush(heap, [0, start])
    dp[start] = 0
    while heap:
        w, n = heappop(heap)
        for n_n, wei in graph[n]:
            n_w = wei + w
            if n_w < dp[n_n]:
                dp[n_n] = n_w
                heappush(heap, [n_w, n_n])

t = int(input())
for _ in range(t):
    n, d, c = map(int ,input().split())
    graph = [[] for _ in range(n + 1)]
    dp = [inf] * (n + 1)
    heap = []
    for _ in range(d):
        a, b, s = map(int, input().split())
        graph[b].append([a, s])

    dijkstra(c, dp, graph)

    cnt = 0
    ans = 0
    for i in dp:
        if i != inf:
            cnt += 1
            ans = max(ans, i)

    print(f"{cnt} {ans}")