概要

全頂点間の最短距離を求め、各都市 \(k\) について

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

を満たす順序付きペア \((i,j)\) の個数を数えます。

考察

都市 \(i,j,k\) がすべて異なるとします。

都市 \(k\) を内部に含む、都市 \(i\) から都市 \(j\) への最短経路が存在するための必要十分条件は、

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

です。

必要性

都市 \(k\) を通る最短経路が存在するとします。その経路を \(k\) の位置で分けると、

• \(i\) から \(k\) までの部分
• \(k\) から \(j\) までの部分

になります。

それぞれのコストは最短距離以上なので、経路全体のコストは

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

以上です。一方、\(i\) から \(k\) への最短経路と、\(k\) から \(j\) への最短経路をつなげれば、

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

です。

元の経路は \(i\) から \(j\) への最短経路であるため、最終的に

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

が成り立ちます。

十分性

反対に、

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

が成り立つとします。

\(i\) から \(k\) への最短経路と、\(k\) から \(j\) への最短経路をつなげると、そのコストは \(d(i,j)\) になります。したがって、これは \(i\) から \(j\) への最短経路であり、都市 \(k\) を内部に含みます。

例えば、

\[ d(i,k)=4,\quad d(k,j)=6,\quad d(i,j)=10 \]

ならば、\(k\) を経由するコストも \(10\) なので、\(k\) を通る最短経路が存在します。\(k\) を通らない別の最短経路があったとしても、「少なくとも1つ」通る最短経路があればよいため数えて構いません。

素朴な方法の問題点

すべての経路を列挙する方法は使えません。同じ都市を複数回通ることが許されているため経路は無数に存在し得ますし、単純路だけに限定してもその個数は指数的になる可能性があります。

また、各ペアについて最短経路を1本だけ復元し、その経路上の都市を数える方法も正しくありません。最短経路が複数ある場合、復元した経路には \(k\) がなくても、別の最短経路には \(k\) が含まれる可能性があるためです。

そこで、具体的な経路を列挙・復元するのではなく、全頂点間の最短距離だけを使って判定します。

アルゴリズム

1. \(N\times N\) の距離配列 dist を用意する。

   • dist[i][i] = 0
   • 道路 \(u\to v\) がある場合は dist[u][v] = w
   • それ以外は到達不能を表す INF

2. Floyd–Warshall 法を用いて、すべての都市の組 \((i,j)\) に対する最短距離 \(d(i,j)\) を求める。

3. 各都市 \(k\) について、すべての順序付きペア \((i,j)\) を調べる。

   • \(i,j,k\) がすべて異なることを確認する。
   • \(i\) から \(k\)、および \(k\) から \(j\) が到達可能であることを確認する。
   • 次の等式が成り立てば、都市 \(k\) の重要度を \(1\) 増やす。

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

1. 各都市の重要度を出力する。

計算量

• 時間計算量: \(O(N^3)\)
  • Floyd–Warshall 法が \(O(N^3)\)
  • 重要度の集計も \(O(N^3)\)
• 空間計算量: \(O(N^2)\)

実装のポイント

• 距離の加算を行うため、距離配列には long long を使用します。
• INF を含む値同士を加算すると、オーバーフローや誤判定の原因になります。そのため、
  • dist[i][k] != INF
  • dist[k][j] != INF

を確認してから加算します。 - 問題では \(i,j,k\) がすべて異なる必要があるため、i == k、j == k、i == j の場合は数えません。 - 最短経路を何本も数えるのではなく、条件を満たす順序付きペア \((i,j)\) を1回だけ数えることに注意します。

ソースコード

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

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

    int N, M;
    cin >> N >> M;

    constexpr long long INF = (1LL << 60);
    vector<vector<long long>> dist(N, vector<long long>(N, INF));

    for (int i = 0; i < N; ++i) dist[i][i] = 0;

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

    for (int k = 0; k < N; ++k) {
        for (int i = 0; i < N; ++i) {
            if (dist[i][k] == INF) continue;
            for (int j = 0; j < N; ++j) {
                if (dist[k][j] == INF) continue;
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    vector<long long> importance(N, 0);

    for (int k = 0; k < N; ++k) {
        for (int i = 0; i < N; ++i) {
            if (i == k || dist[i][k] == INF) continue;
            for (int j = 0; j < N; ++j) {
                if (j == k || j == i || dist[k][j] == INF) continue;
                if (dist[i][j] == dist[i][k] + dist[k][j]) {
                    ++importance[k];
                }
            }
        }
    }

    for (long long answer : importance) {
        cout << answer << '\n';
    }

    return 0;
}

---

この解説は gpt-5.6-sol-high によって生成されました。