BOJ 1753. 最短パス(python)

BOJ 1753. 最短パス(python)

質問リンク
問題の説明
方向図が与えられている場合は、指定された開始点から他のすべての頂点への最短パスを解くプログラムを作成します.ただし、すべての幹線の重み付けは10以下の自然数です.
I/O例

ソリューション

マルチアウトレットを実施する問題

は実装できるが、優先キューを使用すると速度を向上させることができる.

O(V**2) => O(ElogV)

コード#コード#

import sys
import heapq
input = sys.stdin.readline

# 다익스트라 함수
def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    # 시작 노드로 가기 위한 최단 경로는 0으로 설정 후 큐에 삽입
    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]))

# 노드의 개수와 간선의 개수 입력
V, E = map(int, input().split())
INF = int(1e9)
# 시작노드
start = int(input())
# 그래프, 거리 초기화
graph = [[] for _ in range(V + 1)]
distance = [INF] * (V + 1)

# 모든 간선 정보 입력
for _ in range(E):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))

dijkstra(start)

# 시작 노드로부터 갈 수 없는 경우 INF출력
for i in range(1, V + 1):
    if distance[i] == INF:
        print('INF')
    else:
        print(distance[i])