문제

https://www.acmicpc.net/problem/10282

어떤 컴퓨터가 감염되면 해당 컴퓨터에 의존하고 있던 다른 컴퓨터들도 n초 후 감염이 된다. 어떤 특정 컴퓨터에서 감염이 시작되어 마지막으로 감염되는 컴퓨터까지의 시간을 구하면 되는 문제이다!

코드

import heapq

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

def sol(start):
    distance[start]=0
    q=[]
    heapq.heappush(q,(0,start))

    while q:
        t,n=heapq.heappop(q)

        if distance[n]<t:
            continue
        for i in graph[n]:
            cost=t+i[1]
            if cost<distance[i[0]]:
                distance[i[0]]=cost
                heapq.heappush(q,(cost,i[0]))


ans=[]
for _ in range(n):
    n,d,c=map(int,input().split())
    graph=[[] for _ in range(n+1)]
    distance=[INF]*(n+1)
    times=[]    

    for _ in range(d):
        a,b,s=map(int,input().split())
        graph[b].append((a,s))
    sol(c)
    cnt=0
    for d in distance:
        if d<INF:
            cnt+=1
            times.append(d)
    ans.append((cnt,max(times)))

for a in ans:
    print(a[0],a[1])

위의 문제에서 컴퓨터의 개수를 node, 의존성 개수가 edge , 해킹 당한 컴퓨터의 번호를 start로 나타내서 풀었다.

컴퓨터들간의 의존 관계는 a,b,s로 입력받는데 b가 감염되면 a가 s초 후 감염되기 때문에 의존 관계를 나타내는 그래프는 graph[b].append((a,s)) 로 값을 추가했다.

마지막 컴퓨터가 감염되기까지의 시간은 다익스트라 알고리즘으로 감염이 시작된 컴퓨터로 부터 다른 모든 컴퓨터들까지의 최단거리를 구하는 방식으로 풀었다!!

파이팅😴😴😴😴😴!