[BOJ 1753]最短経路(Python)

質問する

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

ある方向図が与えられたとき、始点から他の頂点までの最短距離の問題.
2つの頂点の間に複数の幹線が存在する可能性があることに注意してください.

問題を解く

まず方向図を作成します.

graph = collections.defaultdict(list)

for _ in range(간선 개수):
    # 출발지 u, 도착지 v, 비용 w
    u, v, w = map(int,input().rstrip().rsplit())
    graph[u].append((v,w))

問題では、所定の開始頂点kから他のすべての頂点までの最短距離で解く.

Q = [(0,k)]
dist = collections.defaultdict(int)

そこでQには(開始費用、開始頂点)が加わる.
distリストは、頂点ごとに最短料金を提供します.

while Q:
    cnt, node = heapq.heappop(Q)
    if node not in dist:
        dist[node] = cnt
        for v,w in graph[node]:
            # temp : 현재 정점까지 오는데에 걸린 경로 + 가중치
            temp = cnt + w
            heapq.heappush(Q,(temp,v))

Qの頂点ノードがdistリストにない場合、その頂点に初めてアクセスします.
したがって、dist[node]にはcntが割り当てられる.
この場合,優先キューを用いてnodeとcntを取り出すことが重要である.
Pythonの優先順位キューは基本的に最小hipである.
したがって,同じノードの頂点であれば,より小さなcnt値が最初に取り出される.
🔥 したがって,同じ頂点に対しては,複数の幹線があっても最短距離しか考えられない.
また、頂点nodeに接続された他の頂点vにもアクセスします.정점 node에서 정점 v로 이동할 때 드는 비용 w+24579142を加え、node 까지 이동하는데 든 비용 cnt変数に入れます.
そして、Qにtempを挿入する.
その結果、distリストは、k番頂点からi番インデックスに移動する最短距離のみを格納する.
iが始点でない場合、(temp, 이동한 정점 v)が0であると、移動不可能な頂点が存在することを示すため、dist[i]が出力される.
それ以外にINFを出力します.
Q.dist[i]は0なのに移動できない頂点なのか?
distリストはdist[i]なので、デフォルト値はいずれも0です.
クエリーで接続されたすべての頂点を使用しても、値は変更されません.これは、接続されていない頂点があることを意味します.

コード#コード#

import sys
import collections
import heapq

input = sys.stdin.readline


# 정점 개수 v, 간선 개수 e, 시작정점 k
vc, ec = map(int,input().rstrip().rsplit())
k = int(input().rstrip())
graph = collections.defaultdict(list)

for _ in range(ec):
    u, v, w = map(int,input().rstrip().rsplit())
    graph[u].append((v,w))

Q = [(0,k)]
dist = collections.defaultdict(int)
while Q:
    cnt, node = heapq.heappop(Q)
    if node not in dist:
        dist[node] = cnt
        for v,w in graph[node]:
            # temp : 현재 정점까지 오는데에 걸린 경로 + 가중치
            temp = cnt + w
            heapq.heappush(Q,(temp,v))

# dist 리스트에 저장된 가중치 값을 출력해준다
# 이때 시작점이 아닌데 가중치가 0인값은 경로가 존재하지 않는 경우이므로 INF를 출력한다.
for i in range(1,vc+1):
    if dist[i]==0 and i!=k:
        print("INF")
    else:
        print(dist[i])