[백준] 10282번: 해킹

문제

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

풀이

heap 다익스트라를 응용한 풀이
양수 가중치 단방향성 그래프가 주어지고
출발지점에서 갈 수 있는 가장 끝 지점에 도달할 때까지 최소 거리와
출발지점을 포함하여 방문한 노드수를 구하는 문제

방문한 노드의 수를 카운팅하기 위해서 set 을 사용한 visited 식별자를 만들었다.
현재 위치 까지 이동한 거리가 과거 저장 내역보다 짧으면 재방문 해야하기 때문이다.

import sys
import heapq

INF = sys.maxsize

T = int(input())


def solution(n, c, graph):
    heap = [(0, c)]
    distances = [INF] * (n + 1)
    distances[c] = 0
    virus = set([c])
    time = 0
    while heap:
        cur_distance, cur = heapq.heappop(heap)

        if distances[cur] < cur_distance:
            continue

        for neighbor, weight in graph[cur].items():
            next_distance = cur_distance + weight

            if distances[neighbor] > next_distance:
                distances[neighbor] = next_distance
                heapq.heappush(heap, (next_distance, neighbor))
                virus.add(neighbor)

    for distance in distances:
        if distance == INF: continue
        time = max(time, distance)

    print(len(virus), time)
    return


for _ in range(T):
    n, d, c = map(int, input().rstrip().split(" "))
    graph = {vertex: {} for vertex in range(1, n + 1)}
    for _ in range(d):
        end, start, distance = map(int, input().rstrip().split(" "))
        graph[start][end] = distance

    solution(n, c, graph)