問題
2 種コスト辺の有向グラフで $s \to t$ のパレート最適パスを列挙せよ。
制約
$2 \le N \le 500$
$1 \le M \le 5000$
$0 \le c_i, d_i \le 10^6$
パレート最適パス数 $\le 10^6$
入出力例
入力例 1
4 5
1 4
1 2 1 4
1 3 3 2
2 4 3 1
3 4 1 3
1 4 5 5出力例 1
2
1 5
4 3ヒント (段階的開示)
ヒント1: 方向性
2 次元コストのダイクストラ。状態 $(v, c_1)$ で $c_2$ 最小化。
ヒント2: アプローチ
各頂点のパレートフロンティアを管理。$c_1$ 昇順・$c_2$ 降順リストで支配判定。
ヒント3: 実装
bisect で $O(\log k)$ の支配判定・挿入。遅延削除でキュー中の古いエントリをスキップ。
模範解答 (Python)
import sys
import heapq
import bisect
from collections import defaultdict
def main():
data = sys.stdin.read().split()
ptr = 0
def rd():
nonlocal ptr
v = data[ptr]; ptr += 1
return int(v)
N, M = rd(), rd()
s, t = rd(), rd()
graph = defaultdict(list)
for _ in range(M):
u, v, c, d = rd(), rd(), rd(), rd()
graph[u].append((v, c, d))
INF = float('inf')
pareto_front = [[] for _ in range(N + 1)]
def is_dominated(front, c1, c2):
if not front:
return False
idx = bisect.bisect_right(front, (c1, INF)) - 1
if idx < 0:
return False
return front[idx][1] <= c2
def add_to_front(front, c1, c2):
idx = bisect.bisect_left(front, (c1, -1))
while idx < len(front) and front[idx][1] >= c2:
front.pop(idx)
front.insert(idx, (c1, c2))
pq = [(0, 0, s)]
pareto_front[s] = [(0, 0)]
while pq:
c1, c2, v = heapq.heappop(pq)
idx = bisect.bisect_right(pareto_front[v], (c1, float('inf'))) - 1
dominated = True
if idx >= 0 and pareto_front[v][idx] == (c1, c2):
dominated = False
if dominated:
continue
for u, ec1, ec2 in graph[v]:
nc1, nc2 = c1 + ec1, c2 + ec2
if not is_dominated(pareto_front[u], nc1, nc2):
add_to_front(pareto_front[u], nc1, nc2)
heapq.heappush(pq, (nc1, nc2, u))
result = pareto_front[t]
print(len(result))
for c1, c2 in result:
print(c1, c2)
main()Step-by-Step 解説
1パレート最適
2 次元で他の解に支配されない。
2 次元で他の解に支配されない。
2フロンティア
$c_1$ 昇順 + $c_2$ 降順で管理。
$c_1$ 昇順 + $c_2$ 降順で管理。
3Bi-criteria ダイクストラ
$c_1$ を優先度、各頂点フロンティア更新。
$c_1$ を優先度、各頂点フロンティア更新。
4実装最適化
bisect で $O(\log k)$ の挿入・検索。
bisect で $O(\log k)$ の挿入・検索。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 毎回全探索 | 支配判定が遅い | bisect で $O(\log k)$ |
| 遅延削除忘れ | 古いエントリ処理 | 取り出し時にフロンティア確認 |
| 等値の処理 | $c_1 = c_1'$ のとき | 狭義より広く支配判定 |
次のステップ
- 3 次元・$k$ 次元パレートフロンティア