Overview

Find the shortest paths between all pairs of vertices, and for each city \(k\), count the number of ordered pairs \((i,j)\) satisfying

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

Analysis

Assume that cities \(i, j, k\) are all distinct.

A necessary and sufficient condition for a shortest path from city \(i\) to city \(j\) to pass through city \(k\) internally is

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

Necessity

Suppose there exists a shortest path passing through city \(k\). Splitting this path at \(k\) gives:

• The part from \(i\) to \(k\)
• The part from \(k\) to \(j\)

Since the cost of each part is at least the shortest distance between those endpoints, the total cost of the path is at least

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

On the other hand, concatenating a shortest path from \(i\) to \(k\) and a shortest path from \(k\) to \(j\) yields:

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

Since the original path is a shortest path from \(i\) to \(j\), we ultimately have:

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

Sufficiency

Conversely, suppose that

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

holds.

Concatenating a shortest path from \(i\) to \(k\) and a shortest path from \(k\) to \(j\) gives a path of cost \(d(i,j)\). Therefore, this is a shortest path from \(i\) to \(j\) that internally contains city \(k\).

For example, if

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

then the cost of going through \(k\) is also \(10\), so a shortest path passing through \(k\) exists. Even if there are other shortest paths that do not pass through \(k\), we only need “at least one” shortest path to pass through \(k\), so this pair should be counted.

Drawbacks of Naive Approaches

We cannot use an approach that enumerates all paths. Since visiting the same city multiple times may be allowed, there could be infinitely many paths, and even if restricted to simple paths, the count can be exponential.

Also, reconstructing only one shortest path for each pair and counting the cities on that path is incorrect. If there are multiple shortest paths, the reconstructed path might not contain \(k\), even though another shortest path does contain \(k\).

Therefore, instead of explicitly enumerating or reconstructing paths, we perform the check using only the all-pairs shortest path distances.

Algorithm

1. Prepare an \(N\times N\) distance array dist.

   • dist[i][i] = 0
   • If there is a road \(u\to v\), set dist[u][v] = w
   • Otherwise, set to INF, representing unreachable pairs.

2. Use the Floyd–Warshall algorithm to find the shortest distance \(d(i,j)\) for all pairs of cities \((i,j)\).

3. For each city \(k\), check all ordered pairs \((i,j)\):

   • Check that \(i, j, k\) are all distinct.
   • Check that \(k\) is reachable from \(i\), and \(j\) is reachable from \(k\).
   • If the following equality holds, increment the importance of city \(k\) by \(1\):

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

1. Output the importance of each city.

Complexity

• Time Complexity: \(O(N^3)\)
  • Floyd–Warshall algorithm takes \(O(N^3)\)
  • Aggregating the importance scores also takes \(O(N^3)\)
• Space Complexity: \(O(N^2)\)

Implementation Details

• Use long long for the distance array to handle additions of distances.
• Adding values that include INF can cause overflow or incorrect comparisons. Therefore, make sure that:
  • dist[i][k] != INF
  • dist[k][j] != INF

before performing the addition. - Since the problem requires \(i, j, k\) to be all distinct, do not count cases where i == k, j == k, or i == j. - Note that we count each satisfying ordered pair \((i,j)\) once, rather than counting multiple shortest paths.

Source Code

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

---

This editorial was generated by gpt-5.6-sol-high.