Overview

After finding the shortest distances between all pairs of vertices, for each vertex \(k\), this problem asks us to count the number of pairs of start and end vertices \((i, j)\) such that vertex \(k\) is passed through as an internal vertex on a shortest path between them.

Analysis

First, consider the condition: “there exists at least one shortest path from city \(i\) to city \(j\) that contains city \(k\) as an internal vertex.”

The distance of a path from \(i\) to \(j\) via city \(k\) is the sum of the shortest distance from \(i \to k\) and the shortest distance from \(k \to j\), which is \(d(i, k) + d(k, j)\). For this path to be a shortest path from \(i \to j\), the following equation must hold: $\( d(i, k) + d(k, j) = d(i, j) \)\( When this equation holds, concatenating the shortest path from \)i \to k\( and the shortest path from \)k \to j\( forms a shortest path from \)i \to j\(. Thus, a shortest path containing \)k\( as an internal vertex is guaranteed to exist. Conversely, if this equation does not hold, going through \)k$ will inevitably result in a path longer than the shortest path, so no such valid shortest path exists.

Therefore, for each vertex \(k\), it suffices to check all ordered pairs \((i, j)\) (\(i \neq j \neq k\)) and count the number of pairs that satisfy \(d(i, k) + d(k, j) = d(i, j)\).

Since \(N \leq 250\) is small, precomputing the all-pairs shortest path using the Floyd-Warshall algorithm in \(O(N^3)\) time and then performing an \(O(N^2)\) check for each \(k\) yields an overall \(O(N^3)\) approach, which is well within the time limit.

Algorithm

1. Floyd-Warshall Algorithm: Compute the shortest distance \(d[i][j]\) between all pairs of vertices. Initially, if a direct road exists, set \(d[i][j]\) to its toll/cost; otherwise, set it to infinity (\(\infty\)).
2. Calculating Importance: For each city \(k\), perform the following:
   • Loop over all cities \(i, j\) (\(i \neq k, j \neq k, i \neq j\)).
   • Verify that neither \(d[i][k]\) nor \(d[k][j]\) is \(\infty\) (i.e., a path exists).
   • If \(d[i][k] + d[k][j] == d[i][j]\) holds, the pair \((i, j)\) contributes to the importance of city \(k\), so increment the count by \(1\).
   • After checking all \(i, j\), output the counted value as the importance of city \(k\).

Complexity

• Time Complexity: \(O(N^3)\)
  • Computing the shortest distances using the Floyd-Warshall algorithm takes \(O(N^3)\).
  • Checking all pairs \((i, j)\) for each \(k\) takes \(O(N^3)\).
  • Since \(N \leq 250\), the total number of operations is approximately \(1.5 \times 10^7\), which easily runs within the time limit even in Python.
• Space Complexity: \(O(N^2)\)
  • To store the shortest distance table \(d\).

Implementation Notes

When executing an \(O(N^3)\) calculation in Python, writing naive triple loops may lead to a Time Limit Exceeded (TLE) due to heavy constant factors. The following optimizations can help avoid this: - Cache array rows used in inner loops into local variables to speed up access (e.g., di = d[i], dk = d[k]). - Skip redundant additions and comparisons using an early continue when the distance is \(\infty\). - Extract list elements into variables outside loops to avoid repeated lookups (e.g., dik = d[i][k], dkj = dk[j]).

Source Code

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    INF = float('inf')
    d = [[INF] * (N + 1) for _ in range(N + 1)]
    for i in range(1, N + 1):
        d[i][i] = 0
    for _ in range(M):
        u, v, w = map(int, input().split())
        d[u][v] = w
    # Floyd-Warshall
    for k in range(1, N + 1):
        dk = d[k]
        for i in range(1, N + 1):
            dik = d[i][k]
            if dik == INF:
                continue
            di = d[i]
            dik_plus = dik
            for j in range(1, N + 1):
                v2 = dik_plus + dk[j]
                if v2 < di[j]:
                    di[j] = v2
    out = []
    for k in range(1, N + 1):
        dk = d[k]
        cnt = 0
        for i in range(1, N + 1):
            if i == k:
                continue
            dik = d[i][k]
            if dik == INF:
                continue
            di = d[i]
            for j in range(1, N + 1):
                if j == k or j == i:
                    continue
                dkj = dk[j]
                if dkj == INF:
                    continue
                if dik + dkj == di[j]:
                    cnt += 1
        out.append(str(cnt))
    sys.stdout.write('\n'.join(out))

main()

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