Overview

This problem asks you to find the shortest distances (minimum travel costs) from base \(S\) to all reachable bases, and compute their sum. It reduces to the “single-source shortest path problem” in graph theory.

Analysis

The phrase “the minimum among the travel costs of all paths from base \(S\) to base \(v\)” in the problem statement refers to the shortest distance from source \(S\) to vertex \(v\) in the graph.

A simple breadth-first search (BFS) is one algorithm for finding shortest distances, but it can only be used when all road costs are the same. Since each road has a different cost \(W_i\) in this problem, BFS cannot produce the correct answer.

Another option is the Bellman-Ford algorithm, but its time complexity is \(O(NM)\), which would exceed the time limit (TLE) under the given constraints (\(N, M \le 2 \times 10^5\)).

Noting that all road costs are positive values (\(1 \le W_i \le 10^4\)), this problem can be solved quickly and correctly using Dijkstra’s algorithm.

Algorithm

Dijkstra’s algorithm works by “finalizing distances in order, starting from the closest vertex among those currently known.” To efficiently find the “closest vertex,” it uses a priority queue (heap).

The specific steps are as follows: 1. Prepare an array dist to manage the shortest distance from base \(S\) to each base, initialized to a very large value (\(\infty\)). Set the distance to base \(S\) itself as dist[S] = 0. 2. Insert the starting point information (distance 0, base S) into the priority queue. 3. Repeat the following until the queue is empty: - Extract (tentative distance d, base u) from the queue. - If d is greater than the current dist[u], this is outdated information, so ignore it (skip). - For each base \(v\) connected to base \(u\), compute the distance via base \(u\): nd = d + w. - If nd is less than the current dist[v], update the shortest distance (dist[v] = nd) and add (nd, base v) to the queue. 4. After all exploration is complete, compute and output the sum of distances for all reachable bases (those whose dist is not \(\infty\) and are not \(S\) itself).

Complexity

• Time complexity: \(O((N + M) \log N)\)
  • Each vertex and edge is examined once, and each insertion into and extraction from the priority queue costs \(O(\log N)\), resulting in this overall complexity. It is fast enough even for the maximum case.
• Space complexity: \(O(N + M)\)
  • This is the memory required to hold the adjacency list representing the graph, the array managing distances, and the priority queue.

Implementation Notes

• Using a priority queue In Python, we use the standard library heapq. Since heapq is a data structure (min-heap) that always extracts the smallest value, by storing tuples of (distance, vertex), it automatically extracts the one with the smallest distance first.

• Pruning (skipping unnecessary exploration) It is important to include the check if d > dist[u]: continue when extracting from the queue. This eliminates the waste of processing “outdated (longer) path information” that remains after the shortest distance has already been updated, significantly reducing execution time.

• Fast input reading Since the input size can be very large, calling input() repeatedly becomes slow. By using sys.stdin.read().split() to read all input at once, we eliminate the bottleneck in input processing.

  Source Code

import sys
import heapq

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    S = int(input_data[2])
    
    adj = [[] for _ in range(N + 1)]
    
    idx = 3
    for _ in range(M):
        u = int(input_data[idx])
        v = int(input_data[idx+1])
        w = int(input_data[idx+2])
        adj[u].append((v, w))
        adj[v].append((u, w))
        idx += 3
        
    INF = 10**18
    dist = [INF] * (N + 1)
    dist[S] = 0
    
    hq = [(0, S)]
    
    while hq:
        d, u = heapq.heappop(hq)
        
        if d > dist[u]:
            continue
            
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(hq, (nd, v))
                
    ans = sum(d for i, d in enumerate(dist) if i != 0 and i != S and d != INF)
    print(ans)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3.1-pro-thinking.