해킹 - BOJ

해킹 - BOJ

import heapq

def di(c):
    li = []
    heapq.heappush(li, (0, c))
    dist[c] = 0

    while li:
        cost, node = heapq.heappop(li)
        if dist[node] < cost: continue
        for i in d[node]:
            other = cost + i[1]
            if dist[i[0]] > other:
                dist[i[0]] = other
                heapq.heappush(li, (other, i[0]))


t = int(input())
for _ in range(t):
    n, m, c = map(int, input().split())
    d = [[] for _ in range(n + 1)]
    dist = [float('inf')] * (n + 1)
    for i in range(m):
        a, b, s = map(int, input().split())
        d[b].append((a, s))
    di(c)
    cnt, ret = 0, 0
    for i in range(1, n + 1):
        if dist[i] != float('inf'):
            cnt += 1
            ret = max(ret, dist[i])
    print(cnt, ret)