알고리즘: 백준 10282번 해킹 (feat. python)

 

10282번: 해킹

 

 

import sys
import heapq
INF = sys.maxsize
read = sys.stdin.readline
case = int(read())

def sol():
    n, d, c = map(int, read().split())
    depen = {i:[] for i in range(1, n+1)}
    for _ in range(d):
        a, b, s = map(int, read().split())
        depen[b].append([s, a])
    visit = []
    hq = []

    time = [0] + [INF for _ in range(n)]
    time[c] = 0
    heapq.heappush(hq, [0, c])

    while hq:
        cs, ccom = heapq.heappop(hq)
        if ccom not in visit:
            visit.append(ccom)

            for ns, ncom in depen[ccom]:
                next = ns + cs
                if next < time[ncom]:
                    time[ncom] = next
                    heapq.heappush(hq, [next, ncom])

    else:
        max_time = 0
        for t in time:
            if t != INF and t > max_time:
                max_time = t

        return len(visit), max_time


def pretty(answer):
    for a in answer:
        print(a, end=' ')
    print()


for i in range(case):
    pretty(sol())