概要

\(N\) 個の都市と \(M\) 本の道路からなる有向グラフにおいて、各都市 \(k\) について「都市 \(i\) から都市 \(j\) への最短経路が都市 \(k\) を経由するようなペア \((i, j)\) の個数（都市 \(k\) の重要度）」を求める問題です。 都市の数 \(N \le 250\) と小さいため、ワーシャルフロイド法を用いて全点対最短距離を前計算することで効率的に解くことができます。

考察

1. 「都市 \(k\) を経由する最短経路が存在する」ための条件

都市 \(i\) から都市 \(j\) への最短距離を \(d(i, j)\) と表すことにします。

都市 \(i\) から都市 \(k\) を通って都市 \(j\) へ行く経路の最小コストは \(d(i, k) + d(k, j)\) です。 したがって、都市 \(i\) から都市 \(j\) への最短経路の中に都市 \(k\) を通るものが少なくとも1つ存在する条件は、以下の等式が成り立つことです。

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

すべての道路の通行料（重み）は \(1\) 以上（正の整数）であるため、\(i \neq k\) かつ \(j \neq k\) であれば、都市 \(k\) は必ず始点 \(i\) や終点 \(j\) とは異なる内部の頂点となります。

2. どうやって効率よく計算するか？

毎回最短経路を全探索すると時間がかかってしまいます。 しかし、本問題では都市数 \(N\) が最大でも \(250\) とかなり小さいため、あらかじめすべての都市のペア \((i, j)\) についての最短距離 \(d(i, j)\) を求めておくアプローチが有効です。

全点対最短距離が分かっていれば、各都市 \(k\) について条件 \(d(i, k) + d(k, j) = d(i, j)\) を満たすペア \((i, j)\) を調べるのは単なる二重ループ（\(O(N^2)\)）で済みます。

全点対最短距離は、ワーシャルフロイド法 (Floyd-Warshall algorithm) を用いて \(O(N^3)\) でまとめて求めることができます。

アルゴリズム

1. 初期化:
   • \(N \times N\) の 2次元配列 \(d\) を用意します。
   • 自己への距離 \(d(i, i) = 0\)、直接結ぶ道路がある場合は \(d(u, v) = w\)、それ以外は十分大きな値 \(\infty\) で初期化します。
2. 全点対最短距離の計算 (ワーシャルフロイド法):
   • 3重ループを用いて、すべての頂点対 \((i, j)\) に対する最短距離 \(d(i, j)\) を更新・確定させます。
3. 重要度の集計:
   • 各都市 \(k\)（\(0 \le k < N\)）について、以下を行います。
     • 相異なる都市のペア \((i, j)\)（ただし \(i \neq k, j \neq k, i \neq j\)）をすべて確認します。
     • 都市 \(i\) から都市 \(j\) へ到達可能（\(d(i, j) \neq \infty\)）かつ \(d(i, k) + d(k, j) = d(i, j)\) が成り立つなら、都市 \(k\) の重要度カウントを \(+1\) します。
   • 各都市の重要度を出力します。

計算量

• 時間計算量: \(O(N^3)\)
  • ワーシャルフロイド法に \(O(N^3)\) かかります。
  • 各都市 \(k\) ごとに \(O(N^2)\) のペアを調べるため、重要度の集計全体で \(O(N^3)\) かかります。
  • \(N = 250\) のとき \(N^3 \approx 1.56 \times 10^7\) 回の演算となり、実行時間制限内に余裕で間に合います。
• 空間計算量: \(O(N^2)\)
  • 全点対の最短距離を保持する \(N \times N\) の二次元配列 \(d\) を使用します。

実装のポイント

• インデックスの変換: 入力は \(1\)-indexed（\(1 \dots N\)）ですが、プログラム内では \(0\)-indexed（\(0 \dots N-1\)）に変換して扱うことで配列アクセスがスムーズになります。

• 条件分岐: 条件を満たすペアを数える際、\(i, j, k\) の3つの都市がすべて相異なること（i != k, j != k, i != j）および到達可能であることを必ず判定します。

• Pythonでの高速化: Pythonの多重ループ処理を高速化するため、dk = d[k] や di = d[i] のように行ごとの参照をローカル変数に保持して、配列参照のオーバーヘッドを削減しています。

  ソースコード

import sys

def main():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    
    N = int(data[0])
    M = int(data[1])
    
    INF = 10**18
    d = [[INF] * N for _ in range(N)]
    for i in range(N):
        d[i][i] = 0
        
    idx = 2
    for _ in range(M):
        u = int(data[idx]) - 1
        v = int(data[idx+1]) - 1
        w = int(data[idx+2])
        d[u][v] = w
        idx += 3
        
    # Floyd-Warshall アルゴリズムによる全点対最短経路の計算
    for k in range(N):
        dk = d[k]
        for i in range(N):
            dik = d[i][k]
            if dik == INF:
                continue
            di = d[i]
            for j in range(N):
                if dik + dk[j] < di[j]:
                    di[j] = dik + dk[j]
                    
    # 各都市の重要度の計算
    ans = [0] * N
    for k in range(N):
        dk = d[k]
        count = 0
        for i in range(N):
            if i == k:
                continue
            dik = d[i][k]
            if dik == INF:
                continue
            di = d[i]
            for j in range(N):
                if j == k or j == i:
                    continue
                if di[j] != INF and dik + dk[j] == di[j]:
                    count += 1
        ans[k] = count
        
    print('\n'.join(map(str, ans)))

if __name__ == '__main__':
    main()

この解説は gemini-3.6-flash-high によって生成されました。