Overview

After finding the shortest path costs between all pairs of cities, we determine the condition under which there exists a shortest path passing through city \(k\) using an equality of shortest distances. We use the Floyd–Warshall algorithm for the all-pairs shortest path problem.

Analysis

Let us consider the condition for the existence of a shortest path from city \(i\) to city \(j\) that contains city \(k\) as an intermediate vertex.

If such a shortest path exists, by splitting the path at city \(k\), we can decompose it into two paths:

• From city \(i\) to city \(k\)
• From city \(k\) to city \(j\)

At this time, the following equation holds:

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

Conversely, if this equation holds, we can concatenate a shortest path from city \(i\) to city \(k\) and a shortest path from city \(k\) to city \(j\). Since its total cost is equal to \(d(i,j)\), the concatenated path forms a shortest path passing through city \(k\).

Therefore, when \(i, j, k\) are all distinct, the required condition is

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

For example, if:

• \(d(i,k)=4\)
• \(d(k,j)=7\)
• \(d(i,j)=11\)

then we can construct a path with cost \(11\) passing through city \(k\), meaning a shortest path passing through city \(k\) exists.

On the other hand, if \(d(i,j)=10\), any path passing through city \(k\) has a cost of at least \(11\), so no shortest path passing through city \(k\) exists.

Issues with Naive Approaches

Explicitly enumerating the shortest paths is unsuitable because the number of shortest paths can be extremely large when multiple shortest paths exist.

Furthermore, searching for shortest paths individually for each triple \((i,j,k)\) requires a graph search for each of the up to \(O(N^3)\) triples, which will not finish in time.

Therefore, we first compute the shortest path costs between all pairs of cities in \(O(N^3)\) time using the Floyd–Warshall algorithm. After that, we check the above equation for each \((i,j,k)\). This check also takes \(O(N^3)\) in total.

Algorithm

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

   • Set dist[i][i] = 0.
   • If there is a road \(i \to j\), set dist[i][j] to its toll cost.
   • Otherwise, set it to INF, representing unreachability.

2. Run the Floyd–Warshall algorithm.

Using each city \(k\) as an intermediate vertex, update:

$\( \mathrm{dist}[i][j] = \min\left( \mathrm{dist}[i][j], \mathrm{dist}[i][k]+\mathrm{dist}[k][j] \right) \)$

1. Count the importance for each city \(k\).

   • Skip \(i=k\) as it is outside the condition.
   • Skip cases where \(k\) is unreachable from \(i\).
   • For each \(j\), count it if

   $\( \mathrm{dist}[i][k]+\mathrm{dist}[k][j] = \mathrm{dist}[i][j] \)$

2. However, \(j=k\) is also outside the problem condition. In the code, \(j=k\) is counted once inside the loop, and then excluded by subtracting 1 (count -= 1) for each \(i\).

3. Output the importance of each city.

Complexity

• Time Complexity: \(O(N^3 + M)\), which is \(O(N^3)\) overall
• Space Complexity: \(O(N^2)\)

Implementation Points

• Since the graph is directed, adding a road \(u \to v\) does not update dist[v][u].
• For INF representing unreachability, \(10^{18}\) is used, which is sufficiently larger than any possible shortest path cost.
• i = k is explicitly excluded.
• Regarding j = k, since

$\( \mathrm{dist}[i][k]+\mathrm{dist}[k][k] = \mathrm{dist}[i][k]+0 = \mathrm{dist}[i][k] \)$

always holds, the implementation subtracts 1 right after counting. - j = i is not explicitly excluded, but since all road tolls are positive,

$\( \mathrm{dist}[i][k]+\mathrm{dist}[k][i] > 0 \)$

while \(\mathrm{dist}[i][i]=0\). Thus, the equality does not hold, and it is automatically not counted.

Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    n = next(it)
    m = next(it)

    INF = 10**18
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0

    for _ in range(m):
        u = next(it) - 1
        v = next(it) - 1
        w = next(it)
        dist[u][v] = w

    rng = range(n)

    for k in rng:
        dk = dist[k]
        for i in rng:
            di = dist[i]
            dik = di[k]
            if dik == INF:
                continue
            for j in rng:
                nd = dik + dk[j]
                if nd < di[j]:
                    di[j] = nd

    ans = [0] * n

    for k in rng:
        dk = dist[k]
        count = 0
        for i in rng:
            if i == k:
                continue
            di = dist[i]
            dik = di[k]
            if dik == INF:
                continue

            for j in rng:
                if dik + dk[j] == di[j]:
                    count += 1

            # j = k is always counted above, but endpoints must differ from k.
            count -= 1

        ans[k] = count

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

if __name__ == "__main__":
    main()

---

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