Overview

In a directed graph consisting of \(N\) cities and \(M\) one-way roads, this problem asks us to find, for each city \(k\), the number of ordered pairs \((i,j)\) such that \(k\) is contained as an internal vertex on a shortest path from \(i\) to \(j\) (referred to as its importance).

Analysis

First, a crucial observation is that whether city \(k\) can serve as an internal vertex on a shortest path from \(i\) to \(j\) can be determined solely by the shortest path costs.

Specifically, the following equivalence holds:

City \(k\) (where \(i, j, k\) are distinct) serves as an internal vertex on at least one shortest path from \(i\) to \(j\) \(\iff\) \(d(i,k) + d(k,j) = d(i,j)\)

Why does this hold?

• (\(\Rightarrow\)) If a shortest path passes through \(k\) as an internal vertex, we can split that path at \(k\) into an \(i \to k\) part and a \(k \to j\) part. The cost of each subpath is naturally at least \(d(i,k)\) and \(d(k,j)\) respectively, but since the overall path is a shortest path (cost \(d(i,j)\)), each subpath must also be a shortest path, yielding \(d(i,k) + d(k,j) = d(i,j)\).
• (\(\Leftarrow\)) Conversely, if \(d(i,k)+d(k,j)=d(i,j)\) holds, concatenating a shortest path from \(i \to k\) and a shortest path from \(k \to j\) yields a path from \(i\) to \(j\) of cost \(d(i,j)\). This is a shortest path, and it passes through \(k\) along the way. Since \(i, j, k\) are distinct, \(k\) is indeed an internal vertex.

(Note: Since all road tolls satisfy \(w_i \geq 1\), there are no negative edge weights, so this argument holds directly.)

With this observation, the problem reduces to: “compute the shortest path cost \(d(i,j)\) between all pairs of vertices, and count the pairs satisfying the condition for each \(k\).”

A naive approach of enumerating all actual shortest paths for each pair to check for \(k\) is infeasible because the number of shortest paths can be exponential. The key point is to use the equivalence above to enable checking using only the table of shortest path costs.

Algorithm

1. Compute All-Pairs Shortest Path Costs: Since \(N \leq 250\) is small, use the Floyd–Warshall algorithm to compute all-pairs shortest path costs \(d(i,j)\) in \(O(N^3)\) time.

   • Initialization: \(d(i,i) = 0\), \(d(u,v) = \min(d(u,v), w)\) for each edge \((u,v,w)\), and \(\infty\) otherwise.
   • Update \(d(i,j) = \min(d(i,j),\ d(i,k)+d(k,j))\) for all \(k, i, j\).

2. Compute Importance for Each City: For each \(k\), count the number of ordered pairs \((i,j)\) such that \(i, j, k\) are distinct, \(j\) is reachable from \(i\) (\(d(i,j)\) is finite), and $\(d(i,k) + d(k,j) = d(i,j)\)$ is satisfied.

Pairs where nodes are unreachable do not contribute to any city, so check that \(d(i,k)\), \(d(k,j)\), and \(d(i,j)\) are all finite before checking the equality.

Complexity

• Time Complexity: \(O(N^3)\) (both Floyd–Warshall and the counting step take \(O(N^3)\))
• Space Complexity: \(O(N^2)\) (distance table)

Since \(N \leq 250\), \(N^3 \approx 1.5 \times 10^7\), which is fast enough.

Implementation Details

• Handling INF: To prevent overflow during addition, set INF around 1e18 while checking conditions like d[i][k] == INF before performing addition to skip unreachable pairs (avoiding INF + INF calculations). The maximum possible distance is roughly \((N-1) \text{ edges} \times 10^6 \text{ toll} \approx 2.5 \times 10^8\), so long long can handle it safely with plenty of room.

• Distinctness Condition: Ensure that i == k, j == k, and j == i are excluded during the counting step. Since \(k\) must be an “internal vertex,” it cannot coincide with the starting or ending vertex.

• The condition check is performed using exact equality. \(d(i,k)+d(k,j) < d(i,j)\) is impossible by the definition of shortest paths, and \(>\) simply means no shortest path passes through \(k\), so checking == is sufficient.

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N, M;
    scanf("%d %d", &N, &M);
    const long long INF = 1e18;
    vector<vector<long long>> d(N, vector<long long>(N, INF));
    for(int i=0;i<N;i++) d[i][i]=0;
    for(int e=0;e<M;e++){
        int u,v; long long w;
        scanf("%d %d %lld", &u, &v, &w);
        u--; v--;
        d[u][v]=min(d[u][v], w);
    }
    // Floyd-Warshall
    for(int k=0;k<N;k++){
        for(int i=0;i<N;i++){
            if(d[i][k]==INF) continue;
            long long dik=d[i][k];
            for(int j=0;j<N;j++){
                if(d[k][j]==INF) continue;
                long long nd = dik + d[k][j];
                if(nd < d[i][j]) d[i][j]=nd;
            }
        }
    }
    // For each k, count ordered pairs (i,j), i,j,k distinct, d(i,j) finite,
    // d(i,k)+d(k,j)==d(i,j)
    vector<long long> ans(N,0);
    for(int k=0;k<N;k++){
        long long cnt=0;
        for(int i=0;i<N;i++){
            if(i==k) continue;
            if(d[i][k]==INF) continue;
            long long dik=d[i][k];
            for(int j=0;j<N;j++){
                if(j==k||j==i) continue;
                if(d[k][j]==INF) continue;
                if(d[i][j]==INF) continue;
                if(dik + d[k][j] == d[i][j]) cnt++;
            }
        }
        ans[k]=cnt;
    }
    for(int i=0;i<N;i++) printf("%lld\n", ans[i]);
    return 0;
}

---

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