Overview

Given bases connected by roads, the problem asks to find the shortest distance for each of \(N\) delivery requests \((S_i, T_i)\) and output their total sum.

Analysis

• What we want is “the shortest distances for many source-destination pairs on the same graph.”
  The key point is that the number of queries (delivery requests) \(N=10^5\) is very large.
• A naive approach of “running Dijkstra’s algorithm for each request” costs about \(O(K\log M)\) per run. Repeating this \(10^5\) times is far too slow.
• Here, we notice that the number of bases \(M \le 200\) is small.
  If we precompute the all-pairs shortest distances (shortest distances for all \((u,v)\) pairs), then each request can be answered in \(O(1)\) by simply looking up and adding the value from the table.
• The classic method for all-pairs shortest distances is the Floyd–Warshall algorithm, with a time complexity of \(O(M^3)\).
  For \(M=200\), this is about \(200^3=8,000,000\), which is fast enough.

(Example)
If the number of bases is small, the idea is to precompute all values like “shortest distance from base 1 to base 2,” “shortest distance from base 1 to base 3,” etc., and then for each delivery request, simply look up the corresponding cell.

Algorithm

1. Prepare a distance matrix dist (size \(M \times M\)).
   • Initialize with \(\infty\) (a sufficiently large value)
   • dist[i][i] = 0
2. For each road \((U_j, V_j, W_j)\):
   • dist[U_j][V_j] = W_j, dist[V_j][U_j] = W_j (undirected)
3. Compute all-pairs shortest distances using the Floyd–Warshall algorithm:
   • Incrementally add intermediate vertices \(k\) one by one, applying
     dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) for all \((i,j)\).
4. For each delivery request \((S_i, T_i)\), add dist[S_i][T_i] to the total and output the sum.

Complexity

• Time complexity: \(O(M^3 + N)\)
  (Precomputation is \(O(M^3)\), and adding up each query is \(O(1)\) for a total of \(O(N)\))
• Space complexity: \(O(M^2)\)
  (The distance matrix dist)

Implementation Notes

• Convert indices to 0-based when processing (the input is 1-based).

• Since distances can become very large, use a sufficiently large value such as 10**18 for \(\infty\).

• In the Floyd–Warshall algorithm, skipping updates when dist[i][k] is \(\infty\) provides a slight speedup (the if aik == INF: continue in the code).

• Since the input is large, read it all at once using sys.stdin.buffer.read() to ensure speed.

  Source Code

import sys

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

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

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

    for k in range(M):
        dk = dist[k]
        for i in range(M):
            di = dist[i]
            aik = di[k]
            if aik == INF:
                continue
            for j in range(M):
                nd = aik + dk[j]
                if nd < di[j]:
                    di[j] = nd

    ans = 0
    for _ in range(N):
        s = next(it) - 1
        t = next(it) - 1
        ans += dist[s][t]

    sys.stdout.write(str(ans))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.