Day 063-Q2 — 代数的パス問題（行列半環・熱帯半環 Dijkstra）

2026-06-16 赤色 Master / Phase 8+ ★★★★★★★★★ 半環 / 熱帯半環 / Floyd-Warshall / modular inverse

問題

$N$ 頂点 $M$ 辺の有向グラフが与えられる。各辺 $(u, v)$ には信頼度 $p_{uv} \in (0,1]$（有理数として $a/b$ で与えられる）が付いている。

頂点 $s$ から頂点 $t$ へのパスの信頼度は辺の信頼度の積で定義される。$s$ から $t$ への最大信頼度パスの値を $\bmod 10^9+7$ で出力せよ（分数のまま modular inverse を使って計算）。

$Q$ 個のクエリ $(s_i, t_i)$ に対してそれぞれ答えよ。

制約

パラメータ範囲
$N$$2 \le N \le 300$
$M$$1 \le M \le 5000$
$Q$$1 \le Q \le 10^5$
$a_i, b_i$$1 \le a_i \le b_i \le 10^9$

入出力例

入力例 1

3 3 2
1 2 3 4
2 3 2 3
1 3 1 2
1 3
2 3

出力例 1

500000004
666666672

1→2→3: $\frac{3}{4} \times \frac{2}{3} = \frac{1}{2}$, 1→3: $\frac{1}{2}$（同値）。2→3: $\frac{2}{3}$。 $\frac{1}{2} \bmod 10^9+7 = 500000004$, $\frac{2}{3} \bmod 10^9+7 = 666666672$。

概念図: max-times 半環上の Floyd-Warshall

半環の比較 半環 ⊕ (加法) ⊗ (乗法) min-plus（最短路） 通常のDijkstra/FW min + max-times（本問題） 最大信頼度パス max × max-plus（熱帯半環） 最長路（重みの和） max + Floyd-Warshall は任意の閉じた半環に適用可 対数変換トリック（比較用） max-times を max-plus に変換： $\log(a \times b) = \log a + \log b$ → 積の最大化 = 対数和の最大化 比較: float（対数値）で行う 出力: mod値を別管理 dist_f[i][j]: log値（比較用） dist_m[i][j]: mod値（出力用） modular inverse: $b^{-1} \equiv b^{p-2} \pmod{p}$

ヒント（段階的開示）

ヒント1: 方向性
「最大積パス」は対数に変換すると「最大和パス」。ただし mod 計算が絡むため対数変換は出力には使えない。代わりに熱帯半環の概念を使い、乗算 $\to \otimes$、加算（max）$\to \oplus$ で Floyd-Warshall を行う。
ヒント2: アプローチ
  • 辺の信頼度 $a/b$ の対数 $\log(a/b)$ を float で保持（比較用）
  • mod値 $a \cdot b^{-1} \bmod p$ を別途管理（出力用）
  • Floyd-Warshall で $\max$ 方向に更新：$\text{dist}\_f[i][j] = \max(\text{dist}\_f[i][j], \text{dist}\_f[i][k] + \text{dist}\_f[k][j])$
ヒント3: コード骨格 
for k in range(N):
    for i in range(N):
        if dist_f[i][k] == NEG_INF: continue
        for j in range(N):
            if dist_f[k][j] == NEG_INF: continue
            cand = dist_f[i][k] + dist_f[k][j]  # log の和 = 積の log
            if cand > dist_f[i][j]:
                dist_f[i][j] = cand
                dist_m[i][j] = dist_m[i][k] * dist_m[k][j] % MOD

模範解答 (Python)

import sys, math
input = sys.stdin.readline
MOD = 10**9 + 7

def modinv(a):
    return pow(a, MOD - 2, MOD)

def solve():
    N, M, Q = map(int, input().split())
    NEG_INF = -math.inf
    dist_f = [[NEG_INF] * N for _ in range(N)]
    dist_m = [[0] * N for _ in range(N)]

    for i in range(N):
        dist_f[i][i] = 0.0
        dist_m[i][i] = 1

    for _ in range(M):
        u, v, a, b = map(int, input().split())
        u -= 1; v -= 1
        log_w = math.log(a) - math.log(b)
        mod_w = a * modinv(b) % MOD
        if log_w > dist_f[u][v]:
            dist_f[u][v] = log_w
            dist_m[u][v] = mod_w

    for k in range(N):
        for i in range(N):
            if dist_f[i][k] == NEG_INF:
                continue
            for j in range(N):
                if dist_f[k][j] == NEG_INF:
                    continue
                cand = dist_f[i][k] + dist_f[k][j]
                if cand > dist_f[i][j]:
                    dist_f[i][j] = cand
                    dist_m[i][j] = dist_m[i][k] * dist_m[k][j] % MOD

    out = []
    for _ in range(Q):
        s, t = map(int, input().split())
        s -= 1; t -= 1
        if dist_f[s][t] == NEG_INF:
            out.append(-1)
        else:
            out.append(dist_m[s][t])
    print('\n'.join(map(str, out)))

solve()

Step-by-Step 解説

Step 1: 半環の定義

通常の加算・乗算の代わりに $(R, \max, \times)$ を使う「max-times 半環」（熱帯半環の変種）。パスの「コスト」として対数値を使い比較することで、積の最大化を和の最大化に変換できる。

Step 2: 対数変換によるフロート比較

辺の信頼度 $a/b$ の対数 $\log(a/b)$ を float で保持。比較はこの float 値で行い、実際の出力は mod 演算した値を別途管理する。

Step 3: Floyd-Warshall on 半環

通常の Floyd-Warshall の $+$（加算）を $\times$（乗算）に、$\min$（最小化）を $\max$（最大化）に置き換える。$O(N^3)$ で全点対最大積パスが求まる。

Step 4: modular 逆元による有理数処理

$a/b \bmod p = a \cdot b^{-1} \bmod p$（$b^{p-2} \bmod p$ でフェルマーの小定理）。比較は float の対数で行い、mod 値は別管理。

よくあるミス

ミス原因正しい書き方
比較に mod 値を使う mod は順序を保持しない 比較は log float、出力は mod
対角成分を 1 で初期化し忘れ 自己ループの積は 1 dist_m[i][i] = 1 必須
NEG_INF の伝播チェック漏れ 到達不可能なパスを処理してしまう if dist_f[i][k] == NEG_INF: continue

次のステップ

発展問題: min-plus 半環（通常の最短路）と max-times 半環を統合した「双基準最適パス」を求めよ。

自己評価