Overview

This problem asks us to compute the all-pairs shortest path costs and determine, for each city \(k\), how many pairs of cities \((i, j)\) (where \(i, j, k\) are all distinct) can have city \(k\) as an “interior vertex” on a shortest path between them.

Analysis

Let us consider the condition for city \(k\) to be an “interior vertex” on a shortest path from city \(i\) to city \(j\).

Let \(d(i, k)\) be the shortest path cost from city \(i\) to city \(k\), \(d(k, j)\) be the shortest path cost from city \(k\) to city \(j\), and \(d(i, j)\) be the shortest path cost from city \(i\) to city \(j\). The minimum cost to travel from city \(i\) to city \(j\) passing through city \(k\) can be expressed as \(d(i, k) + d(k, j)\).

If the following condition holds, there exists at least one shortest path from city \(i\) to city \(j\) that passes through city \(k\): $\( d(i, k) + d(k, j) = d(i, j) \quad (d(i, k) \neq \infty, \, d(k, j) \neq \infty) \)$

Even if there are multiple shortest paths, as long as this equation holds, we can conclude that “there exists a shortest path passing through city \(k\),” which fully satisfies the condition in the problem statement.

Since the number of cities \(N\) is small (at most 250), it is fast enough to precompute the shortest distances between all pairs of vertices using the Warshall–Floyd algorithm, and then check all pairs \((i, j)\) for each \(k\).

Algorithm

1. All-Pairs Shortest Path Computation (Warshall–Floyd Algorithm):

   • Initialize the distance array \(d[i][j]\) with a sufficiently large value (\(\text{INF}\)) (except \(d[i][i] = 0\)).
   • Read the road information and set \(d[u_i][v_i] = w_i\).
   • Compute the shortest distance \(d[i][j]\) between all pairs of vertices \((i, j)\) using the Warshall–Floyd algorithm.

2. Counting the Importance of Intermediate Cities:

   • Fix each city \(k\) (\(1 \le k \le N\)).
   • For all pairs of distinct cities \((i, j)\) other than \(k\) (i.e., \(i \neq k\), \(j \neq k\), \(i \neq j\)), check the following:
     • \(d[i][k] \neq \text{INF}\) and \(d[k][j] \neq \text{INF}\) and \(d[i][k] + d[k][j] == d[i][j]\)
   • Count the number of pairs satisfying the condition and output it as the importance of city \(k\).

Complexity

• Time Complexity: \(O(N^3)\)
  • The Warshall–Floyd algorithm takes \(O(N^3)\), and checking all pairs for each \(k\) also takes \(O(N^3)\).
  • Since \(N \le 250\), \(N^3 \approx 1.56 \times 10^7\) loop iterations, which comfortably passes well within the time limit (e.g., 2 seconds).
• Space Complexity: \(O(N^2)\)
  • We use an \(N \times N\) 2D array to store all-pairs distances, resulting in \(O(N^2)\).

Implementation Notes

• Distinctness of vertices \(i, j, k\):

  • By definition in the problem statement, \(i, j, k\) must all be distinct. Make sure to exclude cases where i == k, j == k, or j == i inside the loops.

• Handling Overflow:

  • To prevent overflow when adding \(d[i][k] + d[k][j]\) with the infinity value \(\text{INF}\) (representing unreachable vertices), manage \(\text{INF}\) using a sufficiently large 64-bit integer (such as long long in C++ with 1e18), and check reachability (d[i][k] < INF) before performing addition.

    Source Code

#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;
}

This editorial was generated by gemini-3.6-flash-high.