Overview

A problem where you find the shortest distance from the source to the destination for each delivery request, and output the total sum.

Analysis

In this problem, we need to find the shortest distance for each of multiple delivery requests.
The most straightforward approach is to run Dijkstra’s algorithm for each delivery request, but the number of delivery requests \(N\) can be up to \(10^5\), and running Dijkstra’s algorithm every time may not fit within the time limit (the computational complexity would be \(O(N \cdot M \log M)\), which is approximately \(10^5 \times 200 \log 200\) at maximum).

However, notice that the number of locations \(M\) is at most \(200\), which is small.
This means it is feasible to precompute the shortest distances from all vertices (locations) to all other vertices.
To find such “all-pairs shortest distances,” an effective approach is to run Dijkstra’s algorithm from each vertex as the source.
This way, we can compute all shortest distances in \(O(M \cdot M \log M)\) during preprocessing, and then answer each delivery request in \(O(1)\).

Algorithm

1. Build the graph in adjacency list format (register both directions since roads are bidirectional).
2. Run Dijkstra’s algorithm from each vertex \(i\) (location) as the source, and precompute and store:
   all_dist[i][j] := shortest distance from vertex \(i\) to vertex \(j\)
3. For each delivery request \((S_i, T_i)\), add all_dist[S_i][T_i] to the total sum.
4. Output the total sum.

In the implementation of Dijkstra’s algorithm, Python’s heapq can be used to efficiently extract the vertex with the minimum cost.

Complexity

• Time complexity: \(O(M \cdot (M + K) \log M + N)\)
  • Dijkstra from each vertex: \(M\) times × \(O((M + K) \log M)\)
  • Processing each delivery request: \(O(N)\)
• Space complexity: \(O(M^2 + M + K)\)
  • all_dist: \(M \times M\)
  • Graph adjacency list: \(O(M + K)\)

Implementation Notes

• Location numbers are 1-indexed, so set the array size to M+1.

• When adding bidirectional roads to the graph, make sure to register both directions.

• When initializing Dijkstra’s algorithm, initialize the distance array with float('inf') and set only the source to 0.

• sys.stdin.read is used for fast input reading (not required but recommended).

  Source Code

import heapq
import sys
from collections import defaultdict

def dijkstra(graph, start, M):
    dist = [float('inf')] * (M + 1)
    dist[start] = 0
    pq = [(0, start)]
    
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    
    return dist

def main():
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    
    graph = defaultdict(list)
    
    for _ in range(K):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        w = int(data[idx]); idx += 1
        graph[u].append((v, w))
        graph[v].append((u, w))
    
    # 全点対最短経路を前計算するため、各頂点からダイクストラを行う
    all_dist = [None] * (M + 1)
    for i in range(1, M + 1):
        all_dist[i] = dijkstra(graph, i, M)
    
    total = 0
    for _ in range(N):
        s = int(data[idx]); idx += 1
        t = int(data[idx]); idx += 1
        total += all_dist[s][t]
    
    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.