Overview

In a directed graph consisting of \(N\) cities and \(M\) roads, this problem asks us to find, for each city \(k\), the number of pairs \((i, j)\) such that a shortest path from city \(i\) to city \(j\) passes through city \(k\) (the “importance” of city \(k\)). Since the number of cities \(N \le 250\) is small, we can efficiently solve this problem by precomputing the all-pairs shortest paths using the Floyd-Warshall algorithm.

Analysis

1. Condition for “A Shortest Path Passing Through City \(k\) Exists”

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

The minimum cost of a path from city \(i\) to city \(j\) via city \(k\) is \(d(i, k) + d(k, j)\). Therefore, the condition for at least one shortest path from city \(i\) to city \(j\) to pass through city \(k\) is that the following equality holds:

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

Since all road tolls (weights) are at least \(1\) (positive integers), if \(i \neq k\) and \(j \neq k\), city \(k\) is guaranteed to be an internal vertex distinct from the start \(i\) and end \(j\).

2. How to Compute Efficiently?

Searching all shortest paths every time would take too much time. However, in this problem, the number of cities \(N\) is at most \(250\), which is quite small. Thus, an approach where we precompute the shortest distances \(d(i, j)\) for all pairs of cities \((i, j)\) is effective.

Once the all-pairs shortest distances are known, checking which pairs \((i, j)\) satisfy \(d(i, k) + d(k, j) = d(i, j)\) for each city \(k\) takes just a simple double loop (\(O(N^2)\)).

The all-pairs shortest distances can be computed all at once in \(O(N^3)\) using the Floyd-Warshall algorithm.

Algorithm

1. Initialization:
   • Prepare a 2D array \(d\) of size \(N \times N\).
   • Initialize distance to self \(d(i, i) = 0\), \(d(u, v) = w\) if a direct road exists, and a sufficiently large value \(\infty\) otherwise.
2. All-Pairs Shortest Path Computation (Floyd-Warshall Algorithm):
   • Using a triple loop, update and determine the shortest distance \(d(i, j)\) for all vertex pairs \((i, j)\).
3. Calculating Importance:
   • For each city \(k\) (\(0 \le k < N\)), do the following:
     • Check all distinct city pairs \((i, j)\) (where \(i \neq k, j \neq k, i \neq j\)).
     • If city \(j\) is reachable from city \(i\) (\(d(i, j) \neq \infty\)) and \(d(i, k) + d(k, j) = d(i, j)\) holds, increment the importance count of city \(k\) by \(1\).
   • Output the importance of each city.

Complexity

• Time Complexity: \(O(N^3)\)
  • The Floyd-Warshall algorithm takes \(O(N^3)\).
  • Checking \(O(N^2)\) pairs for each city \(k\) takes \(O(N^3)\) in total for the importance calculation.
  • When \(N = 250\), \(N^3 \approx 1.56 \times 10^7\) operations, which easily fits within the time limit.
• Space Complexity: \(O(N^2)\)
  • Uses an \(N \times N\) 2D array \(d\) to store the all-pairs shortest distances.

Implementation Details

• Index Conversion: The input is \(1\)-indexed (\(1 \dots N\)), but converting it to \(0\)-indexed (\(0 \dots N-1\)) in the program makes array access smoother.

• Conditional Branching: When counting valid pairs, make sure to check that all three cities \(i, j, k\) are distinct (i != k, j != k, i != j) and that reachability is satisfied.

• Optimization in Python: To speed up nested loops in Python, store row references in local variables such as dk = d[k] or di = d[i] to reduce array lookup overhead.

  Source Code

import sys

def main():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    
    N = int(data[0])
    M = int(data[1])
    
    INF = 10**18
    d = [[INF] * N for _ in range(N)]
    for i in range(N):
        d[i][i] = 0
        
    idx = 2
    for _ in range(M):
        u = int(data[idx]) - 1
        v = int(data[idx+1]) - 1
        w = int(data[idx+2])
        d[u][v] = w
        idx += 3
        
    # Floyd-Warshall アルゴリズムによる全点対最短経路の計算
    for k in range(N):
        dk = d[k]
        for i in range(N):
            dik = d[i][k]
            if dik == INF:
                continue
            di = d[i]
            for j in range(N):
                if dik + dk[j] < di[j]:
                    di[j] = dik + dk[j]
                    
    # 各都市の重要度の計算
    ans = [0] * N
    for k in range(N):
        dk = d[k]
        count = 0
        for i in range(N):
            if i == k:
                continue
            dik = d[i][k]
            if dik == INF:
                continue
            di = d[i]
            for j in range(N):
                if j == k or j == i:
                    continue
                if di[j] != INF and dik + dk[j] == di[j]:
                    count += 1
        ans[k] = count
        
    print('\n'.join(map(str, ans)))

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3.6-flash-high.