概要

\(N\) 個の都市と \(M\) 本の一方通行道路からなるグラフにおいて、各都市 \(k\) について「都市 \(i\) から都市 \(j\) への最短経路が内部の頂点として \(k\) を通れるような順序付きペア \((i,j)\) の個数」を求める問題です。

考察

まず「都市 \(k\) が最短経路 \(i \to j\) の内部の頂点として使える」とはどういう条件かを考えます。

ある最短経路 \(c_0=i, c_1, \ldots, c_l=j\) が途中で \(k\) を通るとき、その経路を \(i \to k\) の部分と \(k \to j\) の部分に分けられます。最短経路の部分経路もまた最短経路になる（最短経路の部分構造最適性）ので、

\[d(i,j) = d(i,k) + d(k,j)\]

が成り立ちます。逆に、この等式が成り立てば、「\(i\) から \(k\) への最短経路」と「\(k\) から \(j\) への最短経路」を繋げることで、\(k\) を内部に含む \(i \to j\) の最短経路を1つ構成できます。

つまり、ペア \((i,j)\) が都市 \(k\) の重要度に寄与する条件は、次のようにシンプルに言い換えられます。

\(i, j, k\) が相異なり、\(d(i,k)\) と \(d(k,j)\) がともに有限で、\(d(i,k) + d(k,j) = d(i,j)\) が成り立つ

ここで注意すべき点として、「\(k\) を内部の頂点として含む最短経路が少なくとも1つ存在すればよい」という条件なので、他に \(k\) を通らない最短経路があっても関係ありません。上記の等式が成り立てば必ず \(k\) を通る最短経路が作れるため、この条件だけで判定できます。

したがって、まず全頂点対間の最短距離 \(d(s,t)\) をすべて求めておけば、あとは各 \((i,j,k)\) の三つ組について上記の等式を判定して数え上げるだけです。

アルゴリズム

1. 全点対最短路の計算（Floyd-Warshall法）

\(N \le 250\) と小さいため、全頂点対間の最短距離を Floyd-Warshall 法 で求めます。

• dist[i][j] を都市 \(i\) から都市 \(j\) への最短コストとして初期化します。
  • dist[i][i] = 0
  • 道路 \((u,v,w)\) については dist[u][v] = min(dist[u][v], w)（同じ組の道路は高々1本なので実質そのまま代入）
  • それ以外は \(\infty\)（INF）
• 中継点 \(k\)、始点 \(i\)、終点 \(j\) の三重ループで

\[dist[i][j] \leftarrow \min(dist[i][j],\ dist[i][k] + dist[k][j])\]

と更新します。

2. 各都市の重要度の数え上げ

各中継都市 \(k\) について、\(i, j\) をすべて走査し、

• \(i, j, k\) が相異なる
• \(d(i,k)\) が有限
• \(d(k,j)\) が有限（\(d(i,k)+d(k,j)=d(i,j)\) の等式判定に含まれる）
• \(d(i,k) + d(k,j) = d(i,j)\)

をすべて満たすペア \((i,j)\) の個数を数えます。これがそのまま都市 \(k\) の重要度です。

計算量

• 時間計算量: \(O(N^3)\)
  • Floyd-Warshall が \(O(N^3)\)、数え上げの三重ループ（\(k, i, j\)）も \(O(N^3)\) です。\(N \le 250\) なので \(N^3 \approx 1.5 \times 10^7\) で十分高速です。
• 空間計算量: \(O(N^2)\)
  • 距離行列 dist に \(O(N^2)\) のメモリを使います。

実装のポイント

• 到達不能の扱い: \(i \to j\) への経路が存在しない場合はどの都市の重要度にも寄与しません。距離が INF のペアをスキップすることでこれを自然に処理できます。base + dk[j] == dij の判定では dij が INF のケースを事前に弾くことで、INF 同士の比較による誤カウントを防いでいます。

• 等式判定の順序: d(i,k) が INF なら早期に continue することで無駄な計算を減らせます（コードの if dik >= INF の部分）。

• オーバーフロー: INF を 1 << 60 のような十分大きな値にしておくと、INF 同士の加算をしてしまってもオーバーフローで誤判定が起きにくくなります（Python では多倍長整数なので実害はありませんが、無限大同士の加算が有限値と一致しないように注意します）。ただし本コードでは INF の値は加算前にチェックして弾いているため安全です。

• Python での高速化: 内側ループで dist[k] や dist[i] を dk, di のようにローカル変数へ退避すると、リストアクセスの回数が減り高速になります。\(N=250\) の \(O(N^3)\) を Python で通すための典型的な工夫です。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1

    INF = 1 << 60
    # distance matrix
    dist = [[INF] * N for _ in range(N)]
    for i in range(N):
        dist[i][i] = 0

    for _ in range(M):
        u = int(data[idx]) - 1; idx += 1
        v = int(data[idx]) - 1; idx += 1
        w = int(data[idx]); idx += 1
        if w < dist[u][v]:
            dist[u][v] = w

    # Floyd-Warshall
    for k in range(N):
        dk = dist[k]
        for i in range(N):
            dik = dist[i][k]
            if dik == INF:
                continue
            di = dist[i]
            # inner loop
            for j in range(N):
                nv = dik + dk[j]
                if nv < di[j]:
                    di[j] = nv

    ans = [0] * N

    for k in range(N):
        dk = dist[k]
        cnt = 0
        for i in range(N):
            if i == k:
                continue
            dik = dist[i][k]
            if dik >= INF:
                continue
            di = dist[i]
            base = dik
            for j in range(N):
                if j == k or j == i:
                    continue
                dij = di[j]
                if dij >= INF:
                    continue
                if base + dk[j] == dij:
                    cnt += 1
        ans[k] = cnt

    sys.stdout.write("\n".join(map(str, ans)) + "\n")

main()

---

この解説は claude4.8opus-high によって生成されました。