Overview

This problem asks us to find the total sum of the shortest travel costs from the emergency medical center (base \(S\)) to all reachable bases. This is a classic single-source shortest path problem and can be solved using Dijkstra’s algorithm.

Analysis

Essence of the Problem

This problem requires us to “find the shortest distances from base \(S\) as the starting point to all other reachable bases, and sum them up.” The graph is a weighted undirected graph, and all edge weights are positive (\(W_i \geq 1\)).

Issues with a Naive Approach

If we try to find the shortest distance to each base \(v\) individually using BFS or exhaustive path search, we would need to explore an enormous number of paths, which is far too slow given the constraints where \(N\) and \(M\) can be up to \(2 \times 10^5\).

Additionally, since edges have weights, a simple BFS (breadth-first search) that works for unweighted graphs cannot produce correct shortest distances.

Solution

Since all edge weights are positive, Dijkstra’s algorithm is applicable. By running Dijkstra’s algorithm just once, we can simultaneously find the shortest distances from the starting point \(S\) to all reachable bases.

Algorithm

1. Build the adjacency list: For each base, store a list of pairs consisting of adjacent bases and edge weights.
2. Run Dijkstra’s algorithm:
   • Initialize the distance array dist with all values set to \(\infty\), and set dist[S] = 0.
   • Insert \((0, S)\) into a priority queue (min-heap).
   • Extract the vertex \((d, u)\) with the minimum cost from the queue. If \(d > \text{dist}[u]\), skip it (since a better path has already been found).
   • Otherwise, for each adjacent vertex \(v\) of \(u\), if \(d + w < \text{dist}[v]\), update dist[v] and add \((d + w, v)\) to the queue.
3. Compute the total sum: For all bases \(i\) (\(i \neq S\)), if dist[i] is not \(\infty\) (i.e., the base is reachable), add its value to the total.

Concrete Example

For example, with \(N=3, M=2, S=1\) and edges \((1,2,5)\) and \((2,3,3)\): - \(d(2) = 5\) (base 1 → base 2, cost 5) - \(d(3) = 8\) (base 1 → base 2 → base 3, cost 5+3=8) - Answer: \(5 + 8 = 13\)

Complexity

• Time complexity: \(O((N + M) \log N)\)
  • In Dijkstra’s algorithm, each vertex is finalized at most once, and each edge is used for relaxation at most once. Since each priority queue operation (insertion and extraction) costs \(O(\log N)\), the overall complexity is \(O((N + M) \log N)\).
• Space complexity: \(O(N + M)\)
  • This accounts for the adjacency list, distance array, and priority queue combined.

Implementation Notes

• By using sys.stdin.buffer.read() to read all input at once, input processing can be done efficiently even in Python.

• Using float('inf') as the initial distance value allows for concise detection of unreached vertices.

• The check if d > dist[u]: continue (lazy deletion) is an important optimization technique to avoid reprocessing vertices whose shortest distances have already been finalized. Without this, the same vertex may be processed multiple times, potentially causing TLE.

• Since base numbers range from \(1\) to \(N\), the adjacency list and distance array are sized \(N+1\).

  Source Code

import heapq
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
    S = int(input_data[idx]); idx += 1
    
    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        u = int(input_data[idx]); idx += 1
        v = int(input_data[idx]); idx += 1
        w = int(input_data[idx]); idx += 1
        adj[u].append((v, w))
        adj[v].append((u, w))
    
    INF = float('inf')
    dist = [INF] * (N + 1)
    dist[S] = 0
    pq = [(0, S)]
    
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    
    ans = 0
    for i in range(1, N + 1):
        if i != S and dist[i] != INF:
            ans += dist[i]
    
    print(ans)

main()

---

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