BOJ - 10282 - 해킹

Updated:

import sys
from heapq import heappush, heappop
INF = 1e9
def Dijkstra(K, graph, V):
    heap = []
    distance = [INF] * (V +1)
    distance[K] = 0
    heappush(heap, (0, K))

    while heap:
        weight, location = heappop(heap)

        if distance[location] < weight:
            continue

        for l, w in graph[location]:
            w += weight
            if w < distance[l]:
                distance[l] = w
                heappush(heap, (w, l))

    ret = [0, 0]
    for i in distance:
        if i is not INF:
            ret[0] += 1
            ret[1] = max(i, ret[1])
    print(*ret)

def solution():
    T = int(input())
    for _ in range(T):
        N, D, C = map(int, sys.stdin.readline().split())
        graph = [[] for _ in range(N + 1)]

        for _ in range(D):
            a, b, s = map(int, sys.stdin.readline().split())
            graph[b].append([a, s])

        Dijkstra(C, graph, N)

solution()

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

Categories:

Updated:

Leave a comment