Overview

In a graph consisting of \(N\) cities and \(M\) one-way roads, for each city \(k\), this problem asks us to find the number of ordered pairs \((i,j)\) such that “a shortest path from city \(i\) to city \(j\) can pass through \(k\) as an intermediate vertex”.

Analysis

First, let us consider the condition under which “city \(k\) can be used as an intermediate vertex on a shortest path \(i \to j\)”.

When a shortest path \(c_0=i, c_1, \ldots, c_l=j\) passes through \(k\) along the way, we can split this path into an \(i \to k\) part and a \(k \to j\) part. Since a subpath of a shortest path is also a shortest path (optimal substructure property of shortest paths), we have:

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

Conversely, if this equality holds, by connecting a shortest path from \(i\) to \(k\) and a shortest path from \(k\) to \(j\), we can construct at least one shortest path from \(i\) to \(j\) that contains \(k\) as an intermediate vertex.

In other words, the condition for a pair \((i,j)\) to contribute to the importance of city \(k\) can be rephrased simply as follows:

\(i, j, k\) are pairwise distinct, \(d(i,k)\) and \(d(k,j)\) are both finite, and \(d(i,k) + d(k,j) = d(i,j)\) holds.

Note that the problem only requires that “there exists at least one shortest path containing \(k\) as an intermediate vertex”, so whether there are other shortest paths that do not pass through \(k\) does not matter. If the above equality holds, a shortest path passing through \(k\) can definitely be constructed, so this condition alone is sufficient for checking.

Therefore, if we first compute all-pairs shortest distances \(d(s,t)\), we only need to check the above equality and count the valid pairs for each triplet \((i,j,k)\).

Algorithm

1. Computing All-Pairs Shortest Paths (Floyd-Warshall Algorithm)

Since \(N \le 250\) is small, we can compute all-pairs shortest distances using the Floyd-Warshall algorithm.

• Initialize dist[i][j] as the shortest cost from city \(i\) to city \(j\):
  • dist[i][i] = 0
  • For each road \((u,v,w)\), set dist[u][v] = min(dist[u][v], w) (or simply assign since there is at most one road between the same pair of cities)
  • For all other entries, set to \(\infty\) (INF)
• Using a triple loop over the intermediate city \(k\), start city \(i\), and end city \(j\), update:

\[dist[i][j] \leftarrow \min(dist[i][j],\ dist[i][k] + dist[k][j])\]

2. Counting the Importance of Each City

For each intermediate city \(k\), iterate over all \(i\) and \(j\), and count the number of pairs \((i,j)\) satisfying:

• \(i, j, k\) are pairwise distinct
• \(d(i,k)\) is finite
• \(d(k,j)\) is finite (inherently covered by the equality check \(d(i,k)+d(k,j)=d(i,j)\))
• \(d(i,k) + d(k,j) = d(i,j)\)

This count is precisely the importance of city \(k\).

Complexity

• Time Complexity: \(O(N^3)\)
  • Floyd-Warshall takes \(O(N^3)\), and the triple loop for counting (\(k, i, j\)) also takes \(O(N^3)\). Since \(N \le 250\), \(N^3 \approx 1.5 \times 10^7\), which is fast enough.
• Space Complexity: \(O(N^2)\)
  • The distance matrix dist uses \(O(N^2)\) memory.

Implementation Notes

• Handling Unreachable Cases: If no path exists from \(i \to j\), it does not contribute to the importance of any city. We can naturally handle this by skipping pairs where the distance is INF. In checking equality like base + dk[j] == dij, filtering out cases where dij is INF in advance prevents false counts caused by comparing two INF values.

• Order of Equality Checking: If d(i,k) is INF, skipping early with continue avoids unnecessary calculations (e.g., the if dik >= INF check in code).

• Overflow: Setting INF to a sufficiently large value like 1 << 60 prevents false positive comparisons even if INF values are added together (in Python, arbitrary-precision integers are used so overflow isn’t an issue, but one must still ensure adding infinity to infinity doesn’t accidentally match a finite value). In any case, checking and skipping INF before addition ensures safety.

• Optimization in Python: Aliasing dist[k] or dist[i] into local variables such as dk or di in the inner loop reduces list lookup overhead and speeds up execution. This is a common technique to pass \(O(N^3)\) solutions for \(N=250\) in Python.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1

    INF = 1 << 60
    # distance matrix
    dist = [[INF] * N for _ in range(N)]
    for i in range(N):
        dist[i][i] = 0

    for _ in range(M):
        u = int(data[idx]) - 1; idx += 1
        v = int(data[idx]) - 1; idx += 1
        w = int(data[idx]); idx += 1
        if w < dist[u][v]:
            dist[u][v] = w

    # Floyd-Warshall
    for k in range(N):
        dk = dist[k]
        for i in range(N):
            dik = dist[i][k]
            if dik == INF:
                continue
            di = dist[i]
            # inner loop
            for j in range(N):
                nv = dik + dk[j]
                if nv < di[j]:
                    di[j] = nv

    ans = [0] * N

    for k in range(N):
        dk = dist[k]
        cnt = 0
        for i in range(N):
            if i == k:
                continue
            dik = dist[i][k]
            if dik >= INF:
                continue
            di = dist[i]
            base = dik
            for j in range(N):
                if j == k or j == i:
                    continue
                dij = di[j]
                if dij >= INF:
                    continue
                if base + dk[j] == dij:
                    cnt += 1
        ans[k] = cnt

    sys.stdout.write("\n".join(map(str, ans)) + "\n")

main()

---

This editorial was generated by claude4.8opus-high.