概要

全点対の最短経路コストを計算し、各都市 \(k\) が何種類の都市ペア \((i, j)\) （\(i, j, k\) はすべて相異なる）の最短経路上の「内部の頂点」となり得るかを求める問題です。

考察

都市 \(k\) が、都市 \(i\) から都市 \(j\) への最短経路の「内部の頂点」になり得るための条件を考えます。

都市 \(i\) から都市 \(k\) までの最短コストを \(d(i, k)\)、都市 \(k\) から都市 \(j\) までの最短コストを \(d(k, j)\)、都市 \(i\) から都市 \(j\) までの最短コストを \(d(i, j)\) とします。 都市 \(i\) から都市 \(k\) を経由して都市 \(j\) へ移動する最小のコストは \(d(i, k) + d(k, j)\) と表せます。

このとき、以下の条件を満たしていれば、都市 \(k\) を経由する都市 \(i \to j\) の最短経路が少なくとも1つ存在することになります。 $\( d(i, k) + d(k, j) = d(i, j) \quad (d(i, k) \neq \infty, \, d(k, j) \neq \infty) \)$

最短経路が複数存在する場合でも、この式が成り立っていれば「都市 \(k\) を通る最短経路が存在する」と言えるため、問題文の条件を完全に満たすことができます。

都市数 \(N\) が最大 250 と小さいため、すべての頂点ペア間の最短距離を ワーシャル–フロイド法（Warshall-Floyd Algorithm） であらかじめ計算しておき、各 \(k\) について全ペア \((i, j)\) を判定すれば十分間に合います。

アルゴリズム

1. 全点対最短距離の計算（ワーシャル–フロイド法）:

   • 距離配列 \(d[i][j]\) を十分大きな値（\(\text{INF}\)）で初期化します（ただし \(d[i][i] = 0\)）。
   • 道路の情報を読み込み、\(d[u_i][v_i] = w_i\) と設定します。
   • ワーシャル–フロイド法を用いて、全ての頂点ペア \((i, j)\) 間の最短距離 \(d[i][j]\) を求めます。

2. 中継都市の重要度の集計:

   • 各都市 \(k\) (\(1 \le k \le N\)) を固定します。
   • \(k\) 以外のすべての相異なる都市のペア \((i, j)\)（すなわち \(i \neq k\), \(j \neq k\), \(i \neq j\)）について、以下を判定します。
     • \(d[i][k] \neq \text{INF}\) かつ \(d[k][j] \neq \text{INF}\) かつ \(d[i][k] + d[k][j] == d[i][j]\)
   • 条件を満たすペアの個数をカウントし、都市 \(k\) の重要度として出力します。

計算量

• 時間計算量: \(O(N^3)\)
  • ワーシャル–フロイド法に \(O(N^3)\)、各 \(k\) に対する全ペアの判定に \(O(N^3)\) かかります。
  • \(N \le 250\) であるため、\(N^3 \approx 1.56 \times 10^7\) 回程度のループ処理となり、実行時間制限（2秒など）に余裕で間に合います。
• 空間計算量: \(O(N^2)\)
  • 全点対の距離を保持する \(N \times N\) の二次元配列を使用するため、\(O(N^2)\) となります。

実装のポイント

• 頂点 \(i, j, k\) の相異性:

  • 問題文の定義から、\(i, j, k\) はすべて相異なる必要があります。ループ内で i == k や j == k や j == i のケースを除外することを忘れないようにしましょう。

• オーバーフローへの配慮:

  • 到達不能を表す無限大の値 \(\text{INF}\) と \(d[i][k] + d[k][j]\) の加算時にオーバーフローが起きないよう、\(\text{INF}\) を 1e18 など十分大きな 64bit 整数（C++ の long long）で管理し、到達可能かの判定（d[i][k] < INF）を行ってから加算します。

    ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    const long long INF = 1e18;
    vector<vector<long long>> d(N + 1, vector<long long>(N + 1, INF));

    for (int i = 1; i <= N; ++i) {
        d[i][i] = 0;
    }

    for (int i = 0; i < M; ++i) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        d[u][v] = min(d[u][v], w);
    }

    for (int k = 1; k <= N; ++k) {
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= N; ++j) {
                if (d[i][k] < INF && d[k][j] < INF) {
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
    }

    for (int k = 1; k <= N; ++k) {
        int ans = 0;
        for (int i = 1; i <= N; ++i) {
            if (i == k) continue;
            for (int j = 1; j <= N; ++j) {
                if (j == k || j == i) continue;
                if (d[i][k] < INF && d[k][j] < INF && d[i][k] + d[k][j] == d[i][j]) {
                    ans++;
                }
            }
        }
        cout << ans << "\n";
    }

    return 0;
}

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