概要

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

考察

まず重要な観察として、「都市 \(k\) が \(i\) から \(j\) への最短経路の内部頂点になれるか」は、最短コストだけで判定できるという点があります。

具体的には、次の同値関係が成り立ちます。

都市 \(k\)（\(i, j, k\) は相異なる）が、\(i\) から \(j\) への最短経路のうち少なくとも1つで内部頂点になる \(\iff\) \(d(i,k) + d(k,j) = d(i,j)\)

なぜこれが成り立つのか？

• （\(\Rightarrow\)）ある最短経路が \(k\) を内部頂点として通るなら、その経路を \(k\) で \(i \to k\) 部分と \(k \to j\) 部分に分けられます。それぞれの部分経路のコストは当然 \(d(i,k)\)、\(d(k,j)\) 以上ですが、全体が最短経路（コスト \(d(i,j)\)）である以上、部分経路もそれぞれ最短でなければならず、\(d(i,k) + d(k,j) = d(i,j)\) となります。
• （\(\Leftarrow\)）逆に \(d(i,k)+d(k,j)=d(i,j)\) が成り立つなら、\(i \to k\) の最短経路と \(k \to j\) の最短経路をつなげると、コスト \(d(i,j)\) の \(i\) から \(j\) への経路になります。これは最短経路であり、その途中に \(k\) を通っています。\(i, j, k\) が相異なるので \(k\) はちゃんと内部頂点になります。

（なお、通行料 \(w_i \geq 1\) なのでコストが負になることはなく、この議論がそのまま使えます。）

この観察により、問題は「全点対間の最短コスト \(d(i,j)\) を求めて、各 \(k\) について条件を満たすペアを数える」という形に帰着されます。

素朴に「各ペアについて実際の最短経路を全列挙して \(k\) を探す」ようなアプローチは、最短経路が指数的に存在しうるため現実的ではありません。上の同値変形によって、最短コストの表だけで判定できるようにするのがポイントです。

アルゴリズム

1. 全点対最短コストの計算：\(N \leq 250\) と小さいので、Floyd–Warshall 法で全点対間の最短コスト \(d(i,j)\) を \(O(N^3)\) で求めます。

   • 初期化：\(d(i,i) = 0\)、辺 \((u,v,w)\) について \(d(u,v) = \min(d(u,v), w)\)、それ以外は \(\infty\)。
   • \(d(i,j) = \min(d(i,j),\ d(i,k)+d(k,j))\) を全 \(k, i, j\) について更新。

2. 各都市の重要度の計算：各 \(k\) について、\(i, j, k\) が相異なり、\(i\) から \(j\) へ到達可能（\(d(i,j)\) が有限）で、かつ $\(d(i,k) + d(k,j) = d(i,j)\)\( を満たす順序付きペア \)(i,j)$ を数え上げます。

到達不可能なペアはどの都市にも寄与しないので、\(d(i,k)\)、\(d(k,j)\)、\(d(i,j)\) がすべて有限であることを確認してから判定します。

計算量

• 時間計算量: \(O(N^3)\)（Floyd–Warshall と数え上げの両方が \(O(N^3)\)）
• 空間計算量: \(O(N^2)\)（距離テーブル）

\(N \leq 250\) なので \(N^3 \approx 1.5 \times 10^7\) 程度であり、十分高速です。

実装のポイント

• INF の扱い：加算でオーバーフローしないよう、INF を 1e18 程度にしつつ、加算前に d[i][k] == INF などをチェックして到達不可能な組を飛ばします（INF + INF の計算を避ける）。距離の最大値は「辺 \(N-1\) 本 × 通行料 \(10^6\)」でおよそ \(2.5 \times 10^8\) 程度なので、long long で余裕を持って扱えます。

• 相異なる条件：数え上げで i == k、j == k、j == i を必ず除外します。\(k\) は「内部頂点」であるため、始点・終点と一致してはいけません。

• 判定式は「等号成立」で行います。\(d(i,k)+d(k,j) < d(i,j)\) は最短性の定義上あり得ず、\(>\) なら \(k\) を経由する最短経路が存在しない、というだけなので、単純に == を確認すれば十分です。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N, M;
    scanf("%d %d", &N, &M);
    const long long INF = 1e18;
    vector<vector<long long>> d(N, vector<long long>(N, INF));
    for(int i=0;i<N;i++) d[i][i]=0;
    for(int e=0;e<M;e++){
        int u,v; long long w;
        scanf("%d %d %lld", &u, &v, &w);
        u--; v--;
        d[u][v]=min(d[u][v], w);
    }
    // Floyd-Warshall
    for(int k=0;k<N;k++){
        for(int i=0;i<N;i++){
            if(d[i][k]==INF) continue;
            long long dik=d[i][k];
            for(int j=0;j<N;j++){
                if(d[k][j]==INF) continue;
                long long nd = dik + d[k][j];
                if(nd < d[i][j]) d[i][j]=nd;
            }
        }
    }
    // For each k, count ordered pairs (i,j), i,j,k distinct, d(i,j) finite,
    // d(i,k)+d(k,j)==d(i,j)
    vector<long long> ans(N,0);
    for(int k=0;k<N;k++){
        long long cnt=0;
        for(int i=0;i<N;i++){
            if(i==k) continue;
            if(d[i][k]==INF) continue;
            long long dik=d[i][k];
            for(int j=0;j<N;j++){
                if(j==k||j==i) continue;
                if(d[k][j]==INF) continue;
                if(d[i][j]==INF) continue;
                if(dik + d[k][j] == d[i][j]) cnt++;
            }
        }
        ans[k]=cnt;
    }
    for(int i=0;i<N;i++) printf("%lld\n", ans[i]);
    return 0;
}

---

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