Overview

This problem asks us to determine, in a given weighted directed graph, whether each vertex \(k\) can serve as an intermediate vertex (internal vertex) on the shortest path between other vertex pairs \((i, j)\), and to count the number of pairs satisfying the condition for each \(k\).

Analysis

1. Mathematical Condition for “Being on a Shortest Path”

Let \(d(i, j)\) denote the shortest cost from city \(i\) to city \(j\).

City \(k\) being included as an “internal vertex” on the shortest path from \(i\) to \(j\) means that “the cost of the path from \(i\) to \(j\) via \(k\) equals the overall shortest cost \(d(i, j)\)”. By concatenating the shortest path from \(i\) to \(k\) and the shortest path from \(k\) to \(j\), we can construct an overall shortest path from \(i \to j\).

Therefore, when cities \(i, j, k\) are all distinct, the necessary and sufficient condition for city \(k\) to be on the shortest path from \(i \to j\) is that the following equation holds: $\(d(i, j) = d(i, k) + d(k, j)\)$

2. Constraints and Choice of Approach

To check this condition for all combinations of \(i, j, k\), we need to compute the shortest costs \(d(u, v)\) between all pairs of vertices in advance.

Looking at the constraints, the number of cities \(N\) is relatively small with \(2 \le N \le 400\). Using the Warshall-Floyd algorithm, a well-known algorithm for computing all-pairs shortest paths, we can find the shortest costs between all pairs of vertices in \(O(N^3)\) time complexity.

When \(N = 400\), we have \(N^3 = 6.4 \times 10^7\), which can comfortably fit within the time limit using a fast language such as C++.

Algorithm

The program operates in the following steps:

1. Initialization of the adjacency matrix: Prepare an \(N \times N\) two-dimensional array d, initializing all elements to a sufficiently large value INF (infinity). However, the distance to oneself d[i][i] is set to 0. Then, update d[u][v] = w based on the given road information.

2. Shortest path computation using the Warshall-Floyd algorithm: Run a triple nested loop to find the shortest costs between all pairs of vertices.

   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. Counting the importance: For each city \(k\), iterate over all source vertices \(i\) and destination vertices \(j\). When \(i, j, k\) are all distinct and paths from \(i\) to \(k\) and from \(k\) to \(j\) exist (i.e., are not INF), if the following holds: $\(d(i, j) == d(i, k) + d(k, j)\)\( then increment the importance count of city \)k\( by \)1$.

4. Output of results: Output the count computed for each city \(k\).

Complexity

• Time complexity: \(O(N^3)\) The shortest path computation using the Warshall-Floyd algorithm takes \(O(N^3)\), and counting the importance of each city takes \(O(N^3)\). Since \(N \le 400\), the total computation amounts to approximately \(1.28 \times 10^8\) basic operations, which comfortably fits within the time limit.
• Space complexity: \(O(N^2)\) Since we use an \(N \times N\) two-dimensional array to store the shortest distances between vertices, the space complexity is \(O(N^2)\), which is very lightweight with respect to the memory limit.

Implementation Notes

• Overflow prevention: When using a large value such as 1e18 as INF to represent the absence of a shortest path, we include a condition to verify that d[i][k] != INF && d[k][j] != INF before computing the addition d[i][k] + d[k][j], to prevent overflow.

• Conversion to 0-indexed: While the problem statement gives city numbers from \(1\) to \(N\), within the program we convert (decrement) them to range from \(0\) to \(N-1\) to match array indices, keeping the implementation simple.

  Source Code

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

---

This editorial was generated by gemini-3.5-flash-thinking.