Overview

This problem involves a graph consisting of \(M\) bases and \(K\) roads. For each of \(N\) delivery requests (moving from point \(S_i\) to \(T_i\)), we need to find the shortest distance and compute their total sum.

Analysis

Algorithms for finding shortest distances include Dijkstra’s algorithm and the Floyd-Warshall algorithm. The key characteristic of this problem is that “the number of bases \(M\) is at most 200, which is very small”, while “the number of delivery requests \(N\) is at most \(10^5\), which is very large”.

Why a naive approach doesn’t work

If we compute the shortest path using Dijkstra’s algorithm for each delivery request (across all \(N\) requests), the time complexity would be approximately \(O(N \times (K \log M))\). When \(N = 10^5, K = 2 \times 10^4\), the number of operations exceeds \(10^9\), which won’t fit within the time limit (typically around 2 seconds).

How to solve it

We focus on the fact that \(M\) is small and take the approach of precomputing the shortest distances between all pairs of bases. Once the shortest distances between all pairs of bases are known, each delivery request can be answered by simply “looking up the distance from base \(S_i\) to \(T_i\) in the table,” allowing each query to be answered in \(O(1)\).

To compute the shortest distances between all pairs of bases, the Floyd-Warshall algorithm is optimal.

Algorithm

Floyd-Warshall Algorithm

This algorithm computes the shortest distance for all pairs of bases \((i, j)\).

1. Initialization:
   • Prepare an \(M \times M\) 2D array dist and fill it entirely with infinity (\(\text{INF}\)).
   • Set the distance to oneself dist[i][i] to \(0\).
   • Based on the given road information, record the distances between connected points in dist[u][v] and dist[v][u].
2. Update:
   • Use a triple nested loop, iterating over the intermediate base \(k\), the starting base \(i\), and the ending base \(j\).
   • Compare “the direct distance from \(i\) to \(j\)” with “the distance via \(k\) (\(i \to k \to j\))” and update with the smaller value.
   • Formula: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Computing the Total

The answer is obtained by summing up dist[S_i][T_i] for all requests \((S_i, T_i)\).

Complexity

• Time Complexity: \(O(M^3 + N + K)\)
  • The Floyd-Warshall algorithm takes \(O(M^3)\), reading the roads takes \(O(K)\), and processing the delivery requests takes \(O(N)\).
  • When \(M=200\), \(M^3 = 8,000,000\), which runs sufficiently fast even in Python.
• Space Complexity: \(O(M^2)\)
  • An \(M \times M\) matrix is needed to store the distances between bases.

Implementation Notes

• Optimization in Python:

  • Triple nested loops in Python tend to be slow, so using techniques such as directly referencing lists in the inner loop (assigning to a local variable like di = dist[i]) can reduce execution time.
  • Additionally, skipping unreachable paths with if dik == INF: continue eliminates unnecessary computations.

• Setting a large value (INF):

  • A sufficiently large value must be set for cases where the shortest distance is never updated. In this problem, a value such as \(10^{15}\), which is larger than \(M \times \max(W_j)\), is used.

• Converting from 1-indexed to 0-indexed:

  • The input bases are numbered from \(1\) to \(M\), but for use as array indices, it is convenient to subtract \(1\) and work with indices from \(0\) to \(M-1\).

    Source Code

import sys

def solve():
    # Read all input at once for efficiency
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    if not input_data:
        return
    
    # Convert input data to integers
    data = list(map(int, input_data))
    
    N = data[0]
    M = data[1]
    K = data[2]
    
    # Initialize the distance matrix with a large value (infinity)
    # The maximum possible distance is roughly M * max(W) = 300 * 10^6 = 3 * 10^8
    INF = 10**15
    dist = [[INF] * M for _ in range(M)]
    for i in range(M):
        dist[i][i] = 0
        
    # Process each road and store the distance in the matrix
    # Roads are bidirectional, so we update both dist[u][v] and dist[v][u]
    idx = 3
    for _ in range(K):
        u = data[idx] - 1
        v = data[idx+1] - 1
        w = data[idx+2]
        if w < dist[u][v]:
            dist[u][v] = w
            dist[v][u] = w
        idx += 3
        
    # Floyd-Warshall algorithm to find all-pairs shortest paths
    # Time complexity: O(M^3), which is 300^3 = 27,000,000
    # This is slightly tight for Python but optimized with local variables
    for k in range(M):
        dk = dist[k]
        for i in range(M):
            di = dist[i]
            dik = di[k]
            # Optimization: If node i cannot reach node k, skip the inner loop
            if dik == INF:
                continue
            for j in range(M):
                # Check if the path from i to j through k is shorter than the current path
                new_dist = dik + dk[j]
                if di[j] > new_dist:
                    di[j] = new_dist
    
    # Sum the shortest distances for all N delivery requests
    total_shortest_distance = 0
    for _ in range(N):
        s = data[idx] - 1
        t = data[idx+1] - 1
        total_shortest_distance += dist[s][t]
        idx += 2
        
    # Output the total sum of shortest distances
    sys.stdout.write(str(total_shortest_distance) + '\n')

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-thinking.