[10282] 해킹 in python

> 다익스트라

 

 

해킹된 컴퓨터는 3번

2 -> 1,  2초
3 -> 1, 8초
3 -> 2, 4초

 

2번 컴퓨터가 1번 컴퓨터에 의존하고 있고,

3번 컴퓨터가 1번 컴퓨터에 의존하고 있으며

3번 컴퓨터가 2번 컴퓨터에 의존하고 있다.

 

 

computer[부모]=[(자식1,해킹시간1),(자식2,해킹시간2)...]

computer[1]=[(2,2),(3,8)]

computer[2]=[(1,2)]

computer[3]=[]

 

3번 컴퓨터가 해킹된다.현재 시간은 0초

[지금 시간 + 해킹에 걸리는 시간] 

 

 

 

 

from collections import deque

t = int(input())
for _ in range(t):
    n, d, c = map(int, input().split())  # n= 컴퓨터 개수, d= 의존성 개수, c=해킹당한 컴퓨터의 번호
    computer = {}  # a = 자식 컴퓨터, b = 부모 컴퓨터, s= 해킹당하는 데 걸리는 시간
    for i in range(d):
        a, b, s = map(int, input().split())
        if a not in computer:
            computer[a] = []
        if b not in computer:
            computer[b] = [(a, s)]
            continue
        computer[b].append((a, s))
    time = [1000000000] * (n + 1)
    time[c] = 0
    queue = deque()
    queue.append((0, c))
    while queue:
        now_time, parent = queue.popleft()
        if parent in computer:
            for child, dtime in computer[parent]:
                if time[child] > now_time + dtime:
                    time[child] = now_time + dtime
                    queue.append((now_time + dtime, child))
    answer_cnt, answer_time = 0, 0
    for i in time:
        if i != 1000000000:
            answer_time = max(answer_time, i)
            answer_cnt += 1
    print(answer_cnt, answer_time)