Overview

This problem asks you to find the shortest distance \(d(v)\) from base \(S\) to every reachable base, and output the total sum \(\sum d(v)\). It reduces to the single-source shortest path problem on a weighted undirected graph.

Analysis

• The desired \(d(v)\) is “the minimum travel cost from base \(S\) to base \(v\)” = shortest distance.
• Since all road costs \(W_i\) are positive (\(1 \le W_i\)), Dijkstra’s algorithm can be applied to find the shortest distances.

Why naive approaches fail

• Enumerating “all paths” for each base \(v\) and taking the minimum is impossible. The problem states that the same bases and roads may be traversed any number of times, so the number of paths can grow infinitely.
• BFS only gives correct shortest distances when all edge weights are the same (or \(0/1\)). Since weights can be as large as \(10^4\) in this problem, BFS would result in WA.
• The Bellman–Ford algorithm runs in \(O(NM)\), which is too slow for inputs of scale up to \(2\times 10^5\).

How to solve it

• Use Dijkstra’s algorithm to “efficiently find all shortest distances.”
• Unreachable bases will remain with infinite distance, so at the end we only sum up “those (other than \(S\)) whose distances have been determined.”

(Example)
If \(S \to A\) costs \(5\), \(S \to B\) costs \(2\), and \(B \to A\) costs \(1\), then the shortest path to \(A\) is not the direct \(5\) but \(S\to B\to A\) with cost \(3\). Because of weights, the “path with fewer edges” is not necessarily the shortest.

Algorithm

1. Store the graph as an adjacency list (since it’s undirected, add edges in both directions).
2. Prepare a distance array dist, initialized with dist[S]=0 and all others set to a sufficiently large value (INF).
3. Insert (0, S) into a priority queue (min-heap).
4. Extract the “vertex with the currently smallest distance” from the heap. If its distance is up-to-date (d == dist[u]), adopt it and relax adjacent edges:
   • For edge \((u,v)\) with cost \(w\), compute nd = dist[u] + w
   • If nd < dist[v], update dist[v]=nd and add it to the heap
5. After all processing, sum up only those vertices where \(v \ne S\) and dist[v] < INF, and output the result.

Dijkstra’s algorithm leverages the property that, with positive weights, the distance of a vertex extracted from the heap is guaranteed to be the shortest distance.

Complexity

• Time complexity: \(O((N+M)\log N)\)
  (since heap operations may occur for each edge relaxation)
• Space complexity: \(O(N+M)\)
  (for the adjacency list, distance array, and heap)

Implementation Notes

• Handling unreachable vertices: Vertices whose dist remains INF are not included in the sum.

• Discarding stale heap entries: By including if d != dist[u]: continue, we can ignore outdated distance information (garbage entries added before an update).

• Since the input can be as large as \(2\times 10^5\), the code uses sys.stdin.buffer.read() for fast input.

  Source Code

import sys
import heapq

def ints():
    data = sys.stdin.buffer.read()
    n = len(data)
    i = 0
    while i < n:
        while i < n and data[i] <= 32:
            i += 1
        if i >= n:
            break
        sign = 1
        if data[i] == 45:  # '-'
            sign = -1
            i += 1
        x = 0
        while i < n and data[i] > 32:
            x = x * 10 + (data[i] - 48)
            i += 1
        yield sign * x

it = ints()
try:
    N = next(it)
except StopIteration:
    sys.exit()

M = next(it)
S = next(it) - 1

g = [[] for _ in range(N)]
for _ in range(M):
    u = next(it) - 1
    v = next(it) - 1
    w = next(it)
    g[u].append((v, w))
    g[v].append((u, w))

INF = 10**30
dist = [INF] * N
dist[S] = 0
hq = [(0, S)]

while hq:
    d, u = heapq.heappop(hq)
    if d != dist[u]:
        continue
    for v, w in g[u]:
        nd = d + w
        if nd < dist[v]:
            dist[v] = nd
            heapq.heappush(hq, (nd, v))

ans = 0
for i, d in enumerate(dist):
    if i != S and d < INF:
        ans += d

print(ans)

This editorial was generated by gpt-5.2-high.