Day 083-Q3 — 行列半環上の最短路 + Floyd-Warshall 一般化（代数的経路問題・Kleene スター）

2026-07-06 赤色 Master / Phase 8+ ★★★★★★★★★ 半環・熱帯半環・代数的経路問題・Floyd-Warshall

問題

$N$ 頂点の有向グラフに対して、全頂点対間の 最短距離行列 と 経路数行列（$\text{mod } 998244353$）を同時に求めよ。

距離行列 $D$ と係数行列 $C$ を入力として受け取り、$(d_{ij}, c_{ij})$ の組 $(i \to j$ の最短距離と最短経路数）を出力せよ。

制約

パラメータ範囲備考
$N$$\le 300$頂点数
$d_{ij}$$0 \le d_{ij} \le 10^9$（$-1$ は $\infty$）辺の距離
$c_{ij}$$0 \le c_{ij} \le 10^9$辺の係数

入出力例

入力例1

3
0 1 -1
-1 0 2
3 -1 0
1 1 0
0 1 1
1 0 1

出力例1

0 1 3
5 0 2
3 4 0
1 1 1
1 1 1
1 1 1

概念図: 代数的経路問題の半環構造

半環 $(S, \oplus, \otimes)$ — Floyd-Warshall 一般化 各問題の半環 問題 $\oplus$（加算） $\otimes$（乗算） 単位元 $\bar{1}$ 最短路 $\min$ $+$ $0$ 最長路 $\max$ $+$ $0$ 経路数 $+$ $\times$ $1$ 信頼性 $\max$ $\times$ $1$ 本問（積半環） $(d_1,c_1) \oplus (d_2,c_2)$ $(0,1)$ → 最短距離選択 + 同距離は経路数加算 Floyd-Warshall 半環バージョン for k in range(N): for i in range(N): for j in range(N): dp[i][j] = sadd(dp[i][j], smul(dp[i][k], dp[k][j])) def sadd(a, b): # (d,c) + (d,c) → min-dist & sum-count da,ca = a; db,cb = b if da < db: return a if da > db: return b return (da, (ca+cb)%MOD) ← 同距離なら経路数合算 グラフ例（N=3）: 1 2 3 d=1,c=1 d=2,c=1 d=3,c=1 1→3: min(1+2, 3) = 3 経路数: min は 1+2=3 と 3=3 の2経路 → c=1+1=2

ヒント

ヒント1（方向性）

熱帯半環 $(\mathbb{R} \cup \{\infty\}, \min, +)$ での行列乗算 $[A \otimes B]_{ij} = \min_k (A_{ik} + B_{kj})$ を Floyd-Warshall に適用すれば全対最短路が計算できる。本問では距離と経路数を同時管理するため「積半環」を使う。

ヒント2（アプローチ）

要素 $(d, c)$ の半環で加算・乗算を定義する。加算は「最短距離を選択し、同距離なら経路数を加算」、乗算は「距離を加算し、係数を乗算」。この半環で Floyd-Warshall を動かせば最短距離と経路数が同時に求まる。

ヒント3（ほぼ答え） 
MOD = 998244353
INF = float('inf')

def sadd(a, b):
    da, ca = a; db, cb = b
    if da < db: return a
    if da > db: return b
    return (da, (ca + cb) % MOD)

def smul(a, b):
    da, ca = a; db, cb = b
    if da == INF or db == INF: return (INF, 0)
    return (da + db, ca * cb % MOD)

# Floyd-Warshall on semiring
for k in range(N):
    for i in range(N):
        ik = dp[i][k]
        if ik[0] == INF: continue
        for j in range(N):
            dp[i][j] = sadd(dp[i][j], smul(ik, dp[k][j]))

模範解答

import sys
input = sys.stdin.readline

def solve():
    MOD = 998244353
    INF = float('inf')
    N = int(input())

    dist_raw = []
    for _ in range(N):
        row = list(map(int, input().split()))
        dist_raw.append(row)

    count_raw = []
    for _ in range(N):
        row = list(map(int, input().split()))
        count_raw.append(row)

    dp = [[(INF, 0)] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            d = dist_raw[i][j]
            c = count_raw[i][j]
            if i == j:
                dp[i][j] = (0, 1)
            elif d == -1:
                dp[i][j] = (INF, 0)
            else:
                dp[i][j] = (d, c % MOD)

    def sadd(a, b):
        da, ca = a; db, cb = b
        if da < db: return a
        if da > db: return b
        return (da, (ca + cb) % MOD)

    def smul(a, b):
        da, ca = a; db, cb = b
        if da == INF or db == INF: return (INF, 0)
        return (da + db, ca * cb % MOD)

    for k in range(N):
        for i in range(N):
            ik = dp[i][k]
            if ik[0] == INF:
                continue
            for j in range(N):
                dp[i][j] = sadd(dp[i][j], smul(ik, dp[k][j]))

    for i in range(N):
        row = []
        for j in range(N):
            d = dp[i][j][0]
            row.append('-1' if d == INF else str(d))
        print(' '.join(row))

    for i in range(N):
        row = []
        for j in range(N):
            d, c = dp[i][j]
            row.append('0' if d == INF else str(c))
        print(' '.join(row))

solve()

Step-by-Step 解説

Step 1: 代数的経路問題のフレームワーク

問題半環$\oplus$$\otimes$
最短路熱帯半環$\min$$+$
最長路最大・加算$\max$$+$
経路数通常$+$$\times$
信頼性確率$\max$$\times$

Step 2: 積半環での同時計算

def sadd(a, b):
    da, ca = a; db, cb = b
    if da < db: return a
    if da > db: return b
    return (da, (ca + cb) % MOD)

Step 3: Floyd-Warshall の適用 $O(N^3)$

for k in range(N):    # 中間頂点
    for i in range(N):
        for j in range(N):
            dp[i][j] = sadd(dp[i][j], smul(dp[i][k], dp[k][j]))

よくあるミス

ミス原因正しい書き方
対角成分を (0,0) で初期化自己ループ経路数が 0 になる対角を (0, 1) で初期化
INF + INF でオーバーフロー整数 INF 使用時float('inf') または加算前に INF チェック
経路数 mod を取り忘れ巨大数の発生(ca + cb) % MOD
k の外側に i,j ループFloyd-Warshall の順序違反for k: for i: for j: が正しい順序

次のステップ

  • 発展問題: 辺に $\{0,1\}$ の正規表現ラベルを付けて全対間のパス言語を求めよ（Kleene スター演算子）
  • 参考: Gondran & Minoux (1984) "Graphs and Algorithms"

自己評価

理解度: / /

自分の回答:

気づき・メモ: