概要

この問題は、与えられた重み付き有向グラフにおいて、各頂点 \(k\) が他の頂点ペア \((i, j)\) の最短経路上の中継地点（内部の頂点）になり得るかを判定し、条件を満たすペアの個数を各 \(k\) について求める問題です。

考察

1. 「最短経路上に存在する」ことの数理的条件

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

都市 \(k\) が \(i\) から \(j\) への最短経路の「内部の頂点」として含まれるとは、「\(i\) から \(k\) を経由して \(j\) に至る経路のコストが、全体の最短コスト \(d(i, j)\) と等しくなる」ということです。 \(i\) から \(k\) への最短経路と、\(k\) から \(j\) への最短経路を繋ぎ合わせることで、全体として \(i \to j\) の最短経路が構成できます。

したがって、都市 \(i, j, k\) がすべて相異なるとき、都市 \(k\) が \(i \to j\) の最短経路に含まれるための必要十分条件は、以下の式が成り立つことです。 $\(d(i, j) = d(i, k) + d(k, j)\)$

2. 制約とアプローチの選択

この条件をすべての \(i, j, k\) の組み合わせに対して判定するためには、すべての頂点ペア間の最短コスト \(d(u, v)\) をあらかじめ求めておく必要があります。

制約に注目すると、都市の数 \(N\) は \(2 \le N \le 400\) と比較的小さいです。 全点対間の最短経路を求める代表的なアルゴリズムであるワーシャル・フロイド（Warshall-Floyd）法を使用すると、時間計算量 \(O(N^3)\) で全点対間の最短コストを求めることができます。

\(N = 400\) のとき \(N^3 = 6.4 \times 10^7\) となり、C++などの高速な言語であれば、実行時間制限内に余裕を持って間に合わせることができます。

アルゴリズム

プログラムは以下のステップで動作します。

1. 隣接行列の初期化: \(N \times N\) の二次元配列 d を用意し、すべての要素を十分に大きな値 INF（無限大）で初期化します。ただし、自分自身への距離 d[i][i] は 0 とします。 その後、与えられた道路の情報を元に d[u][v] = w と更新します。

2. ワーシャル・フロイド法による最短経路の計算: 3重のループを回し、すべての頂点ペア間の最短コストを求めます。

   for (int k = 0; k < N; ++k) {
      for (int i = 0; i < N; ++i) {
          for (int j = 0; j < N; ++j) {
              d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
          }
      }
   }
   

3. 重要度のカウント: 各都市 \(k\) について、始点 \(i\) と終点 \(j\) を全探索します。 \(i, j, k\) がすべて相異なり、かつ \(i\) から \(k\)、\(k\) から \(j\) への経路が存在する（INF でない）とき、 $\(d(i, j) == d(i, k) + d(k, j)\)\( が成り立つならば、都市 \)k\( の重要度のカウントを \)1$ 増やします。

4. 結果の出力: 各都市 \(k\) について求めたカウントを出力します。

計算量

• 時間計算量: \(O(N^3)\) ワーシャル・フロイド法による最短経路の計算に \(O(N^3)\)、各都市の重要度のカウントに \(O(N^3)\) かかります。\(N \le 400\) であるため、全体の計算量は約 \(1.28 \times 10^8\) 回の基本演算となり、実行時間制限に十分間に合います。
• 空間計算量: \(O(N^2)\) 頂点間の最短距離を保持する \(N \times N\) の二次元配列を使用するため、空間計算量は \(O(N^2)\) となり、メモリ制限に対しても非常に軽量です。

実装のポイント

• オーバーフローの防止: 最短経路が存在しないことを表す INF の値として 1e18 などの大きな値を使用する場合、d[i][k] + d[k][j] の足し算でオーバーフローが発生しないよう、事前に d[i][k] != INF && d[k][j] != INF であることを確認する条件式を入れています。

• 0-indexed への変換: 問題文では都市の番号が \(1\) から \(N\) で与えられますが、プログラム内では配列のインデックスに合わせて \(0\) から \(N-1\) に変換（デクリメント）して処理を行うことで、実装をシンプルにしています。

  ソースコード

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

using namespace std;

const long long INF = 1e18;

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

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

    vector<vector<long long>> d(N, vector<long long>(N, INF));
    for (int i = 0; i < N; ++i) {
        d[i][i] = 0;
    }

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

    for (int k = 0; k < N; ++k) {
        for (int i = 0; i < N; ++i) {
            for (int j = 0; 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 = 0; k < N; ++k) {
        int count = 0;
        for (int i = 0; i < N; ++i) {
            if (i == k) continue;
            for (int j = 0; j < N; ++j) {
                if (j == k || j == i) continue;
                if (d[i][k] != INF && d[k][j] != INF && d[i][j] == d[i][k] + d[k][j]) {
                    count++;
                }
            }
        }
        cout << count << "\n";
    }

    return 0;
}

---

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