백준 10282 : 문제링크

  • 문제유형 :

    • 그래프
    • 다익스트라 최단 경로 알고리즘

  • 설명

    • 정점의 개수 N, 간선의 개수 D
    • 우선순위 큐를 이용하여, 시간복잡도 O(NlogD)로 해결할 수 있습니다

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    import heapq
    import sys
    input = sys.stdin.readline

    def dijkstra(strat):
        heap_data = []
        heapq.heappush(heap_data, (0, start))
        distance[start] = 0
        while heap_data:
            dist, now = heapq.heappop(heap_data)
            if distance[now] < dist:
                continue
            for i in adj[now]:
                cost = dist + i[1]
                if distance[i[0]] > cost:
                    distance[i[0]] = cost
                    heapq.heappush(heap_data, (cost, i[0]))

    for _ in range(int(input())):
        n, m, start = map(int, input().split())
        adj = [[] for i in range(n + 1)]
        distance = [1e9] * (n + 1)
        for _ in range(m):
            x, y, cost = map(int, input().split())
            adj[y].append((x, cost))
        dijkstra(start)
        count = 0
        max_distance = 0
        for i in distance:
            if i != 1e9:
                count += 1
                if i > max_distance:
                    max_distance = i
        print(count, max_distance)