[Baekjoon] 1753. 最短経路[G 5]

📚 質問する

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

📖 に答える

FloydWarsalアルゴリズムを学習する際に見られるマルチタスクアルゴリズムです.
1つの頂点で最短パスを探すときに使用します.

📌 「マルチサンプルアルゴリズム」を参照してください。

https://m.blog.naver.com/ndb796/221234424646
多翼点アルゴリズムの核心は、頂点から接続されたすべての頂点を決定し、最も近い頂点から開始することである.
近い頂点が聞こえてから別の頂点に到達すると、その頂点の値がより速く変更されます.交換後、最も近い頂点を再度確認し、繰り返し交換します.
配列の大きさが大きく、隣接マトリクスであればメモリオーバーフローが発生します!
したがって、それを隣接テーブルとして使用する必要があります.
多極値アルゴリズムは、頂点を決定するたびに最大値を変更するので、最大値の決定を続行します.従ってhipで実現することは非常に効率的である.
お尻にノードの最高値を加えると、お尻に同じノードが複数積み上げられます.頂点からの距離は常に変更されているため、取り出されたノードと保存されたノードの距離が異なる場合は、以前に配置された頂点になります.そのため、取り出してお尻から投げ続けるだけです.
heapに残りのノードがない場合は、終了します.

📒 コード#コード#

import heapq
import sys
input = sys.stdin.readline

n, e = map(int, input().split())        # 정점과 간선의 수
INF = n * 10                            # 나올 수 있는 가장 큰 값보다 크게 설정
arr = [[] for _ in range(n + 1)]
start = int(input().rstrip())           # 시작점
dp = [0 for _ in range(n + 1)]
for _ in range(e):                      # 가중치에 관한 그래프
    a, b, w = map(int, input().split())
    arr[a].append((w, b))               # 행 -> 열 일 때 값은 가중치

dp = [INF for _ in range(n + 1)]        # 시작점에서의 최단 거리
dp[start] = 0                           # 시작점은 0이다.

heap = []
heapq.heappush(heap, (0, start))        # 시작점을 담고 시작
while heap:
    w, v = heapq.heappop(heap)
    if dp[v] != w:                      # 변경된 값과 다르면 pass
        continue
    for t_w, t_v in arr[v]:
        if dp[t_v] > t_w + w:           # 최소값으로 넣어준다.
            dp[t_v] = t_w + w
            heapq.heappush(heap,(t_w + w, t_v))

for i in range(1, n + 1):
    print('INF' if dp[i] == INF else dp[i])

🔍 結果