Overview

Given a road network between bases, this problem asks you to calculate the total sum of multiple delivery requests (finding the shortest distance between pairs of bases).

Analysis

The problem requires finding the total sum of \(N\) delivery requests (shortest distance from \(S_i\) to \(T_i\)). Since \(N\) can be as large as \(10^5\), computing the shortest path for each individual request is inefficient. On the other hand, the number of bases \(M\) is at most \(200\), which is small. Therefore, it is appropriate to solve this as an “all-pairs shortest path problem” by precomputing and storing the shortest distances between all pairs of bases. This allows each request to be answered in \(O(1)\) by looking up the precomputed results.

Algorithm

We use the Floyd–Warshall algorithm to compute the shortest distances between all pairs of bases. The Floyd–Warshall algorithm uses dynamic programming to update shortest distances by sequentially considering intermediate bases.

1. Initialize the adjacency matrix dist[i][j] (0 for the same base, the road distance if directly connected, and a sufficiently large value otherwise)
2. Update the shortest distances between all pairs of bases by considering routing through each base \(k\):
   • For all \(i\), \(j\), update with dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
3. Sum up the precomputed dist[S_i][T_i] for all delivery requests

Complexity

• Time complexity: \(O(M^3 + N)\)
  • The Floyd–Warshall part is \(O(M^3)\)
  • Processing the delivery requests is \(O(N)\)
• Space complexity: \(O(M^2)\)
  • A two-dimensional array is needed to store the distances between bases

Implementation Notes

• During initialization, set the distance between the same base to 0, and for directly connected roads, take the minimum value (although the problem may not have multiple roads between the same pair of bases, this handles the case where multiple direct roads exist)

• By initializing with a sufficiently large value (\(10^{18}\)), unreachable cases are represented (though the problem guarantees reachability)

• Input reading is optimized using sys.stdin.read and an iterator

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    N = int(next(it)); M = int(next(it)); K = int(next(it))
    
    graph = [[] for _ in range(M+1)]
    for _ in range(K):
        u = int(next(it)); v = int(next(it)); w = int(next(it))
        graph[u].append((v, w))
        graph[v].append((u, w))
    
    dist = [[10**18] * (M+1) for _ in range(M+1)]
    for i in range(1, M+1):
        dist[i][i] = 0
        
    for i in range(1, M+1):
        for neighbor, weight in graph[i]:
            dist[i][neighbor] = min(dist[i][neighbor], weight)
    
    for k in range(1, M+1):
        for i in range(1, M+1):
            if dist[i][k] == 10**18:
                continue
            for j in range(1, M+1):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    total = 0
    for _ in range(N):
        s = int(next(it)); t = int(next(it))
        total += dist[s][t]
    
    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.