Overview

This problem asks us to find the shortest costs between all pairs of cities, determine for each city \(k\) whether it can be passed through as an intermediate vertex on a shortest path between a pair of other cities \((i, j)\), and count the number of such pairs.

Analysis

If we consider an approach that enumerates all shortest paths for every pair \((i, j)\) as described in the problem statement and checks whether city \(k\) is included in them, it will result in TLE (Time Limit Exceeded) or MLE (Memory Limit Exceeded) because the number of shortest paths can be extremely large.

Here, we focus on an important property of shortest paths. What is the condition for “city \(k\) is included as an intermediate vertex on a shortest path from city \(i\) to city \(j\)”? This means that connecting a shortest path from city \(i\) to \(k\) and a shortest path from \(k\) to \(j\) yields one of the shortest paths from \(i\) to \(j\). In other words, this is equivalent to \(d(i, k) + d(k, j) = d(i, j)\) holding true (where \(d(x, y)\) represents the shortest cost from \(x\) to \(y\)).

Proof: - (\(\Rightarrow\)) If there exists a shortest path containing \(k\), the first half from \(i\) to \(k\) and the second half from \(k\) to \(j\) must each be a shortest path (if either were not a shortest path, replacing that segment with a shorter path would decrease the total cost, creating a contradiction). Therefore, \(d(i, k) + d(k, j) = d(i, j)\) holds. - (\(\Leftarrow\)) If \(d(i, k) + d(k, j) = d(i, j)\) holds, concatenating a shortest path from \(i\) to \(k\) and a shortest path from \(k\) to \(j\) yields a shortest path from \(i\) to \(j\) containing \(k\) as an intermediate vertex.

However, according to the problem definition, \(i, j, k\) must all be distinct, and paths from \(i\) to \(k\) and from \(k\) to \(j\) must exist (\(d(i, k) < \infty, d(k, j) < \infty\)).

Therefore, once we compute the all-pairs shortest path costs \(d\), we only need to count the pairs \((i, j)\) satisfying the conditions for each \(k\) by exhaustive search.

Algorithm

1. All-Pairs Shortest Path Calculation: Compute the shortest cost \(d(i, j)\) for all pairs of cities \((i, j)\) using the Floyd-Warshall algorithm. Initially, set the toll \(w\) if a direct road exists, and a sufficiently large value (INF) otherwise. The distance to oneself, \(d(i, i)\), is 0.
2. Calculation of Importance for Each City: For each city \(k\), count the number of pairs of distinct cities \((i, j)\) satisfying the following conditions:
   • \(i \neq k\), \(j \neq k\), and \(i \neq j\)
   • \(d(i, k) \neq \infty\) and \(d(k, j) \neq \infty\)
   • \(d(i, k) + d(k, j) = d(i, j)\)

Complexity

• Time Complexity: \(O(N^3)\)
  • The Floyd-Warshall algorithm runs in \(O(N^3)\).
  • Checking all pairs \((i, j)\) for each \(k\) also takes \(N \times N \times N = O(N^3)\).
  • Since \(N \leq 250\), the loop runs \(N^3 = 1.5625 \times 10^7\) times, which comfortably finishes within the time limit.
• Space Complexity: \(O(N^2)\)
  • To store the shortest distance table \(d\).

Implementation Points

• INF Setting and Overflow Prevention: During the Floyd-Warshall processing or condition checking, addition involving INF values for unreachable paths may occur. Using long long types and setting INF to a sufficiently large value such as \(10^{18}\) will prevent overflow.

• Reachability Check: If d[i][k] or d[k][j] is INF, no path exists, so exclude it from the computation. In the code, performing an early continue such as if (d[i][k] == INF) continue; allows safe and fast processing.

• Covering All Conditions: When counting pairs \((i, j)\), cases where i == k, j == k, or i == j must be explicitly excluded. In the code, this can be achieved using if (i == k) continue; or if (j == k || j == i) continue;.

  Source Code

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

This editorial was generated by or-glm-5.2-high.