Atcoder 競プロ典型 90 問 013 - Passing（★5）
問題文は👆を確認してください
導入
atcoderで精進してますが、
どこかにアウトプットしたかったので、qiitaに書くことにしました。
ACしてから載せるようにしてますが、考え方が至っていない点があればご指摘頂けると幸いです。
また、誰かの参考になると嬉しいです。
使用しているアルゴリズム
ダイクストラ法（Dijkstra法）
- 開始地点（
start）を起点として、各地点への最短経路（dest）を返却する - 開始地点から繋がっている無向辺を全て調べて、隣接するノードに最短コストで到達できるかをチェックする
- 既に
dest[to]に格納されている最短距離が、今のルートよりも短い場合はスキップ（枝刈り） -
heapq（優先度付きキュー）を使用して、コストが小さい順に探索を進めることで、全体の計算量を
O((N + M) log N)に抑えている - 素朴に
cost昇順にリストソートしていたらO(N^2)近くになって間に合わないため、heapqによる改善は必須
解法のポイント
この問題は、グラフ上で「各都市を中継点としたときに1番目の都市からN番目の都市へ行く最短距離」を求めるものです。
ポイントは以下の通りです：
-
無向グラフの表現：
bectorsという辞書に、各都市から繋がっている隣接都市と距離を記録します。これはdefaultdict(list)を使って構築。 - ダイクストラ法の利用：開始都市（1番目）から各都市への最短距離、およびゴール都市（N番目）から各都市への最短距離をそれぞれ計算します。
-
中継点を全探索：都市
kを経由したときの合計距離はdest1[k] + destN[k]になります。これを全都市について計算して出力すれば良いです。 -
計算量：
O((N+M) log N)が2回なので、十分に許容範囲内です（N, M ≤ 10^5）。
ACサンプル
def dijkstra(bectors,start,N):
import heapq
# 各ノードまでの最短距離を無限大で初期化
dest = [float('inf')] * N
dest[start] = 0
# 優先度付きキュー（コスト昇順）
q = []
heapq.heappush(q,(0,start))
while q:
cost,p = heapq.heappop(q)
# 既に最短距離より長い場合はスキップ
if dest[p] < cost:
continue
# pから行ける隣接ノードを全探索
nexts = bectors[p]
for m,to in nexts:
if dest[to] > cost + m:
dest[to] = cost + m
heapq.heappush(q,(cost + m,to))
return dest
from collections import defaultdict
N,M = map(int, input().split())
bectors = defaultdict(list)
# 無向グラフの構築（0-indexed）
for _ in range(M):
a,b,m = map(int, input().split())
a,b = a-1,b-1
bectors[a].append((m,b))
bectors[b].append((m,a))
# 1番目の都市（0）から各都市までの最短距離
dest1 = dijkstra(bectors,0,N)
# N番目の都市（N-1）から各都市までの最短距離
destN = dijkstra(bectors,N-1,N)
# 各都市kを経由したときの最短距離を出力
for i in range(N):
r = dest1[i] + destN[i]
print(r)