概要

全ての都市間の最短コストを求めた上で、各都市 \(k\) が他の都市のペア \((i, j)\) の最短経路の途中（内部の頂点）として通過可能かどうかを判定し、そのようなペアの数を数える問題です。

考察

問題文の通りに各ペア \((i, j)\) の最短経路を全て列挙し、その中に都市 \(k\) が含まれるかを調べるアプローチを考えると、最短経路の数は非常に多くなり得るため、TLE（時間制限超過）やメモリ不足になります。

ここで、最短経路の重要な性質に注目します。 「都市 \(k\) が都市 \(i\) から都市 \(j\) への最短経路の内部の頂点として含まれる」とは、どういう条件でしょうか？ 都市 \(i\) から \(k\) への最短経路と、\(k\) から \(j\) への最短経路を繋げたものが、\(i\) から \(j\) への最短経路の1つになるということを意味します。 言い換えると、\(d(i, k) + d(k, j) = d(i, j)\) が成り立つことと同値です（ここで \(d(x, y)\) は \(x\) から \(y\) への最短コストを表します）。

証明： - (\(\Rightarrow\)) \(k\) を含む最短経路が存在するなら、その経路の前半で \(i\) から \(k\) へ行く部分と、後半で \(k\) から \(j\) へ行く部分はそれぞれ最短経路でなければなりません（もし最短でなければ、その部分を別の最短経路に置き換えることで全体のコストが下がってしまい、矛盾するため）。したがって \(d(i, k) + d(k, j) = d(i, j)\) が成り立ちます。 - (\(\Leftarrow\)) \(d(i, k) + d(k, j) = d(i, j)\) が成り立つなら、\(i\) から \(k\) への最短経路と \(k\) から \(j\) への最短経路を繋げば、\(k\) を内部の頂点として含む \(i\) から \(j\) への最短経路となります。

ただし、問題文の定義より、\(i, j, k\) はすべて異なる必要があり、また \(i\) から \(k\)、および \(k\) から \(j\) への経路が存在すること（\(d(i, k) < \infty, d(k, j) < \infty\)）が必要です。

したがって、まず全点対最短コスト \(d\) を求めてしまえば、各 \(k\) について、条件を満たす \((i, j)\) の組を全探索で数えるだけでよいことが分かります。

アルゴリズム

1. 全点対最短経路の計算: ワーシャル・フロイド法を用いて、全ての都市のペア \((i, j)\) についての最短コスト \(d(i, j)\) を計算します。 初期状態では、直接道路がある場合はその通行料 \(w\) を、ない場合は十分に大きな値（INF）を設定します。自分自身への距離 \(d(i, i)\) は 0 です。
2. 各都市の重要度の計算: 各都市 \(k\) について、以下の条件を満たす異なる都市のペア \((i, j)\) の個数を数えます。
   • \(i \neq k\) かつ \(j \neq k\) かつ \(i \neq j\)
   • \(d(i, k) \neq \infty\) かつ \(d(k, j) \neq \infty\)
   • \(d(i, k) + d(k, j) = d(i, j)\)

計算量

• 時間計算量: \(O(N^3)\)
  • ワーシャル・フロイド法が \(O(N^3)\)。
  • 各 \(k\) について全ペア \((i, j)\) を調べる処理も \(N \times N \times N = O(N^3)\)。
  • \(N \leq 250\) なので、\(N^3 = 1.5625 \times 10^7\) 回のループとなり、制限時間内に十分処理できます。
• 空間計算量: \(O(N^2)\)
  • 最短距離テーブル \(d\) を保持するため。

実装のポイント

• INFの設定とオーバーフロー対策: ワーシャル・フロイド法の処理中や条件判定時において、到達不能な経路の距離として INF 同士の足し算が発生する可能性があります。long long 型を使用し、INF は \(10^{18}\) などの十分に大きな値を設定することでオーバーフローを防ぎます。

• 到達可能性のチェック: d[i][k] や d[k][j] が INF の場合、経路が存在しないため計算から除外します。コード内では if (d[i][k] == INF) continue; などとして事前に continue することで、安全かつ高速に処理できます。

• 条件の網羅: ペア \((i, j)\) を数える際、i == k や j == k、i == j の場合を確実に除外する必要があります。コード内では if (i == k) continue; や if (j == k || j == i) continue; でこれを実現しています。

  ソースコード

#include <iostream>
#include <vector>

using namespace std;

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

    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) {
            if (d[i][k] == INF) continue;
            for (int j = 1; j <= N; ++j) {
                if (d[k][j] == INF) continue;
                if (d[i][k] + d[k][j] < d[i][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
    }

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

    return 0;
}

この解説は or-glm-5.2-high によって生成されました。