[백준] 10282번 해킹

💡문제접근

• a → b : 컴퓨터 a가 컴퓨터 b를 의존한다.
• 컴퓨터 b가 감염되면 s초 후에 컴퓨터 a가 감염되는 것이므로 graph[b].apped([a, s])로 코드를 작성해야한다.
• 위의 의존성 개념에 대해서 이해를 하는데 시간이 조금 걸렸다.

💡코드(메모리 : 50040KB, 시간 : 868ms)

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance = [INF] * (n+1)
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

    computer_cnt = 0
    time = 0
    for i in range(1, n+1):
        if distance[i] != INF:
            computer_cnt += 1
            time = max(time, distance[i])
    print(computer_cnt, time)

T = int(input())
for _ in range(T):
    n, d, c = map(int, input().strip().split())
    graph = [[] for _ in range(n+1)]
    for _ in range(d):
        a, b, s = map(int, input().strip().split())
        graph[b].append([a, s])
    dijkstra(c)

💡소요시간 : 47m