Overview

This problem is a shortest path problem on a graph where we need to find the minimum travel cost from base S to all other bases and calculate their total sum.

Analysis

In this problem, we need to find the minimum travel cost d(v) for all bases v reachable from base S. This is a typical single-source shortest path problem that requires an efficient algorithm.

As a naive approach, we might consider depth-first search or breadth-first search, but since the edge weights have positive values, simple BFS/DFS cannot correctly find the shortest paths. Additionally, the Bellman-Ford algorithm has a time complexity of O(N*M), and since N and M can be as large as 200,000, it would not meet the time limit.

In this problem, since the edge weights are non-negative, we can solve it efficiently using Dijkstra’s algorithm.

Algorithm

We use Dijkstra’s algorithm to compute the shortest distances from base S to all other bases. The specific steps are as follows:

1. Initialize the distance to each base as infinity (INF), and set the distance to the starting point S to 0
2. Use a priority queue (min-heap) to process bases in order of smallest distance
3. For each neighboring base of the current base, update the distance if the new path distance is smaller than the current distance
4. After processing all bases, sum up the distances of all reachable bases other than S

Dijkstra’s algorithm correctly finds shortest paths when edge weights are non-negative, and its time complexity is efficient.

Complexity

• Time complexity: \(O((N + M) \log N)\) (standard complexity of Dijkstra’s algorithm using a priority queue)
• Space complexity: \(O(N + M)\) (memory required for the graph representation and distance array)

Implementation Notes

• Since the input values are large, use sys.stdin.read() for fast input processing

• Subtract 1 from the input base numbers to process in 0-indexed format

• Use a sufficiently large value (\(10^{18}\)) as the initial distance

• When a distance popped from the priority queue differs from the current distance, skip the processing to avoid unnecessary computation

• Be careful not to include unreachable bases (distance equals INF) in the total sum

  Source Code

import heapq
import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(0)
        return
        
    it = iter(data)
    n = int(next(it)); m = int(next(it)); s = int(next(it)) - 1
    
    graph = [[] for _ in range(n)]
    for _ in range(m):
        u = int(next(it)) - 1
        v = int(next(it)) - 1
        w = int(next(it))
        graph[u].append((v, w))
        graph[v].append((u, w))
    
    INF = 10**18
    dist = [INF] * n
    dist[s] = 0
    heap = [(0, s)]
    
    while heap:
        d, node = heapq.heappop(heap)
        if d != dist[node]:
            continue
        for neighbor, weight in graph[node]:
            new_d = d + weight
            if new_d < dist[neighbor]:
                dist[neighbor] = new_d
                heapq.heappush(heap, (new_d, neighbor))
                
    total = 0
    for i in range(n):
        if i != s and dist[i] != INF:
            total += dist[i]
            
    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.