問題
$N$ 頂点 $M$ 辺の有向重み付きグラフが与えられる。頂点 $1$ から頂点 $N$ への K番目に短い単純パス の長さを求めよ。
制約
$2 \le N \le 400$
$1 \le M \le N(N-1)$
$1 \le K \le 20$
$1 \le w_i \le 10^6$
入出力例
入力例 1
5 8 3
1 2 2
1 3 4
2 3 1
2 4 5
3 4 2
3 5 6
4 5 3
1 5 15出力例 1
9ヒント (段階的開示)
ヒント1: 方向性
Yen's Algorithm: 前回の最短路に deviation を加えて探索。$O(KN(M + N\log N))$。
ヒント2: アプローチ
$i$ 番目のパスから各頂点 $v$ を spur node として:1. $v$ より前は root path で固定。2. 以前と同じ辺を禁止。3. $v$ から N へダイクストラ。4. root+spur を候補として PQ に。
ヒント3: 誘導
def dijkstra(src, banned_nodes, banned_edges):
# 通常のダイクストラに禁止条件を追加模範解答 (Python)
import heapq
import sys
def solve():
input_data = sys.stdin.read().split()
idx = 0
N, M, K = int(input_data[idx]), int(input_data[idx+1]), int(input_data[idx+2])
idx += 3
adj = [[] for _ in range(N + 1)]
for _ in range(M):
u, v, w = int(input_data[idx]), int(input_data[idx+1]), int(input_data[idx+2])
idx += 3
adj[u].append((v, w))
def dijkstra(src, banned_nodes, banned_edges):
dist = [float('inf')] * (N + 1)
dist[src] = 0
pq = [(0, src, [src])]
while pq:
d, v, path = heapq.heappop(pq)
if d > dist[v]: continue
if v == N: return d, path
for u, w in adj[v]:
if u in banned_nodes or (v, u) in banned_edges: continue
nd = d + w
if nd < dist[u]:
dist[u] = nd
heapq.heappush(pq, (nd, u, path + [u]))
return float('inf'), []
d, path = dijkstra(1, set(), set())
if d == float('inf'):
print(-1); return
A = [(d, path)]
B = []
for i in range(K - 1):
last_path = A[-1][1]
for j in range(len(last_path) - 1):
spur_node = last_path[j]
root_path = last_path[:j+1]
root_cost = sum(
next(w for u2, w in adj[last_path[x]] if u2 == last_path[x+1])
for x in range(j)
)
banned_edges = set()
banned_nodes = set(root_path[:-1])
for prev_dist, prev_path in A:
if prev_path[:j+1] == root_path:
banned_edges.add((prev_path[j], prev_path[j+1]))
for cand_dist, cand_path in B:
if cand_path[:j+1] == root_path:
if j+1 < len(cand_path):
banned_edges.add((cand_path[j], cand_path[j+1]))
spur_dist, spur_path = dijkstra(spur_node, banned_nodes, banned_edges)
if spur_dist < float('inf'):
total_cost = root_cost + spur_dist
full_path = root_path[:-1] + spur_path
if (total_cost, full_path) not in B:
heapq.heappush(B, (total_cost, full_path))
if not B:
print(-1); return
best = heapq.heappop(B)
A.append(best)
print(A[K-1][0])
solve()Step-by-Step 解説
1Yen's Algorithm の直感
K番目最短路は「前の最短路に少し変更を加えた」パス。各頂点を spur node として別経路を探す。
K番目最短路は「前の最短路に少し変更を加えた」パス。各頂点を spur node として別経路を探す。
2Root path と Spur path
Root path: spur node より前（固定）。Spur path: spur node から目的地まで新経路。
Root path: spur node より前（固定）。Spur path: spur node から目的地まで新経路。
3禁止条件
同じ root path で以前使ったパスと同じ「次の辺」を禁止 → 重複パス防止。
同じ root path で以前使ったパスと同じ「次の辺」を禁止 → 重複パス防止。
4計算量
$O(KN(M + N \log N))$。
$O(KN(M + N \log N))$。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 禁止条件で root path の比較が不正確 | list の比較コスト | tuple化してハッシュ比較 |
| 同じパスをキューに複数回追加 | 重複チェック漏れ | 追加前に if not in B を確認 |
| root_cost のインデックスずれ | j-1 と j の混同 | range(j) で丁寧に確認 |
次のステップ
- 発展: 制約なし K番目最短路（拡張ダイクストラ）
- K番目最短閉路