Overview

This is a problem where, on a graph consisting of \(M\) bases, you need to find the shortest distance for each of \(N\) delivery requests and output their total sum. The key insight is that \(M\) is small (at most 200), so by precomputing the shortest distances between all pairs of bases, the problem can be solved efficiently.

Analysis

Naive Approach and Its Issues

One could consider computing the shortest distance using Dijkstra’s algorithm for each delivery request. Since one run of Dijkstra’s algorithm has a complexity of about \(O(K \log M)\), running it for all \(N\) requests results in \(O(N \cdot K \log M)\). With \(N\) up to \(10^5\), this leads to many redundant computations unless we apply optimizations such as grouping requests with the same starting base.

Key Observation: \(M\) is Small

This problem has the constraint \(M \leq 200\). This is a condition where the Floyd-Warshall algorithm, which computes all-pairs shortest distances, is extremely well-suited.

Using the Floyd-Warshall algorithm, we can precompute the shortest distances between all pairs of bases in \(O(M^3)\). When \(M = 200\), \(M^3 = 8 \times 10^6\), which is sufficiently fast.

Once the precomputation is done, the shortest distance for each delivery request can be determined by simply looking up the table (\(O(1)\)).

Algorithm

Floyd-Warshall Algorithm

This is an algorithm for computing the shortest distances between all pairs of vertices. It works as follows:

1. Initialization: Prepare an \(M \times M\) distance table dist.

   • dist[i][i] = 0 (the distance from a vertex to itself is 0)
   • If an edge \((u, v)\) with weight \(w\) exists, set dist[u][v] = dist[v][u] = w
   • Otherwise, set dist[i][j] = ∞

2. Update via triple nested loop: Try each intermediate vertex \(k\) from \(0\) to \(M-1\), and for every pair of vertices \((i, j)\), perform the following update: $\(\text{dist}[i][j] = \min(\text{dist}[i][j],\; \text{dist}[i][k] + \text{dist}[k][j])\)\( This checks "Is it shorter to go from vertex \)i\( to vertex \)j\( via vertex \)k$?”

3. Query answering: For each delivery request \((S_i, T_i)\), look up dist[S_i][T_i] and compute the total sum.

Concrete Example

Suppose there are 3 bases and roads “1-2 (distance 3)”, “2-3 (distance 5)”, and “1-3 (distance 10)”:

• In the initial table, dist[1][3] = 10
• Going via intermediate vertex \(k = 2\): dist[1][2] + dist[2][3] = 3 + 5 = 8 < 10
• Therefore, dist[1][3] is updated to 8

Complexity

• Time complexity: \(O(M^3 + N)\)
  • \(O(M^3)\) for the Floyd-Warshall algorithm, \(O(N)\) for answering \(N\) queries
  • Since \(M \leq 200\), \(M^3 = 8 \times 10^6\), which is sufficiently fast
• Space complexity: \(O(M^2)\)
  • Required for storing the distance table

Implementation Notes

• Conversion to 0-indexed: Since the input base numbers are 1-based, we subtract 1 internally to use 0-based indexing consistently.

• Fast input processing: By reading all input at once with sys.stdin.buffer.read() and splitting with split(), we prevent input from becoming a bottleneck even in Python.

• Pruning: When dist[i][k] == INF, we skip the inner loop to avoid unnecessary computations.

• Local variable references: By assigning list references to local variables such as dk = dist[k] and di = dist[i], we speed up Python’s list access.

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1

    INF = float('inf')
    dist = [[INF] * M for _ in range(M)]
    for i in range(M):
        dist[i][i] = 0

    for _ in range(K):
        u = int(input_data[idx]) - 1; idx += 1
        v = int(input_data[idx]) - 1; idx += 1
        w = int(input_data[idx]); idx += 1
        if w < dist[u][v]:
            dist[u][v] = w
            dist[v][u] = w

    # Floyd-Warshall
    for k in range(M):
        dk = dist[k]
        for i in range(M):
            dik = dist[i][k]
            if dik == INF:
                continue
            di = dist[i]
            for j in range(M):
                val = dik + dk[j]
                if val < di[j]:
                    di[j] = val

    total = 0
    for _ in range(N):
        s = int(input_data[idx]) - 1; idx += 1
        t = int(input_data[idx]) - 1; idx += 1
        total += dist[s][t]

    print(total)

main()

---

This editorial was generated by claude4.6opus-thinking.