Day 080-Q5 — DAG 最長パス + 辞書順最小経路復元（トポロジカルDP）

問題

$N$ 頂点 $M$ 辺の DAG が与えられる。各辺には正の重みがある。

頂点 $s$ から頂点 $t$ への 最長重み付きパス の長さと、そのパスが複数ある場合は 辞書順最小の経路 を出力せよ。

$s$ から $t$ への有向パスが存在しない場合は -1 を出力。

入出力例

5 6 1 5
1 2 3
1 3 1
2 4 2
3 4 5
4 5 1
2 5 4

7
1 2 5

概念図: 順方向 DP と逆方向 DP で辞書順最小経路を特定

ヒント

# 経路復元: 辞書順最小
path = [s]
cur = s
while cur != t:
    nxt = -1
    for v, w in sorted(adj[cur], key=lambda x: x[0]):
        if dist[cur] + w + rev_dist[v] == dist[t]:
            nxt = v
            break
    path.append(nxt)
    cur = nxt

模範解答

import sys
from collections import deque
input = sys.stdin.readline

def solve():
    N, M, s, t = map(int, input().split())
    s -= 1; t -= 1
    adj = [[] for _ in range(N)]
    in_deg = [0] * N
    for _ in range(M):
        u, v, w = map(int, input().split())
        u -= 1; v -= 1
        adj[u].append((v, w))
        in_deg[v] += 1

    # Kahn's トポロジカルソート
    topo = []
    q = deque(i for i in range(N) if in_deg[i] == 0)
    while q:
        u = q.popleft()
        topo.append(u)
        for v, _ in adj[u]:
            in_deg[v] -= 1
            if in_deg[v] == 0:
                q.append(v)

    INF = float('-inf')

    # 順方向 DP
    dist = [INF] * N
    dist[s] = 0
    for u in topo:
        if dist[u] == INF: continue
        for v, w in adj[u]:
            if dist[u] + w > dist[v]:
                dist[v] = dist[u] + w

    if dist[t] == INF:
        print(-1)
        return

    # 逆方向 DP
    rev_dist = [INF] * N
    rev_dist[t] = 0
    for u in reversed(topo):
        for v, w in adj[u]:
            if rev_dist[v] != INF and rev_dist[v] + w > rev_dist[u]:
                rev_dist[u] = rev_dist[v] + w

    print(dist[t])

    # 辞書順最小経路復元
    path = [s]
    cur = s
    while cur != t:
        nxt = -1
        for v, w in sorted(adj[cur], key=lambda x: x[0]):
            if (dist[cur] + w <= dist[t] and
                rev_dist[v] != INF and
                dist[cur] + w + rev_dist[v] == dist[t]):
                nxt = v
                break
        if nxt == -1:
            break
        path.append(nxt)
        cur = nxt

    print(*[x+1 for x in path])

solve()

Step-by-Step 解説

Step 1: トポロジカルソート

Kahn's Algorithm（BFS ベース）で入次数ゼロの頂点から順に処理。$O(N + M)$。

Step 2: 最長パス DP（順方向）

dist[v] を $s$ から $v$ への最長距離として初期化（$-\infty$）。トポロジカル順に更新する。

Step 3: 最長パス DP（逆方向）

rev_dist[v] を $v$ から $t$ への最長距離として計算。トポロジカル順の逆順で処理する。

Step 4: 辞書順最小経路の復元

$cur$ にいるとき、次の頂点 $v$ は：

• dist[cur] + w + rev_dist[v] == dist[t]（最長パスの一部）
• 上記を満たす $v$ のうち最小のものを選ぶ（辞書順最小）

辺を $v$ の番号でソートして最初にマッチしたものを貪欲選択。

Step 5: 時間計算量

トポロジカルソート + 順逆 DP: $O(N + M)$。経路復元: $O(N \log M)$（各ステップで辺をソート）。全体 $O((N + M) \log M)$。

よくあるミス

次のステップ

• 発展問題: $K$ 番目最短パス列挙（Yen's Algorithm + 辞書順）
• 関連: DAG の最長パス + セグメント木区間更新 $O(N \log N)$

自己評価