Overview

Given an undirected graph, find the shortest distance from a specified starting vertex \(S\) to each other vertex, and output their total sum.

Analysis

This problem is a classic “single-source shortest path problem,” where we need to find the shortest distances from the starting vertex \(S\) to all other vertices.

As a naive approach, we could try depth-first search or breadth-first search to explore all paths, but since the number of vertices \(N\) and edges \(M\) can be up to \(2 \times 10^5\), such exploration is too computationally expensive and cannot be solved within the time limit (TLE).

Additionally, since the edges have weights, simple BFS cannot correctly determine the shortest distances (WA).

Therefore, noting that the edge weights are non-negative, it is appropriate to use Dijkstra’s algorithm. Dijkstra’s algorithm can efficiently find shortest paths by using a priority queue.

Furthermore, since we are told that unreachable vertices can be ignored, we simply need to add only the vertices where \(d(v) \neq \infty\) to the total sum.

Algorithm

1. Graph Construction: Build the undirected graph using an adjacency list. Since each edge can be traversed in both directions, add edges in both directions.
2. Applying Dijkstra’s Algorithm:
   • Prepare a distance array dist to manage distances from the starting vertex \(S\), initialized to \(\infty\) for all vertices except \(S\), which is set to \(0\).
   • Using a priority queue (heap), extract the currently closest vertex and update the distances to its adjacent vertices.
3. Aggregating Results: Iterate over vertices \(1\) through \(N\), and sum up \(d(v)\) for all reachable vertices (\(d(v) \neq \infty\)) other than \(S\).

Complexity

• Time complexity: \(O((N + M) \log N)\)
  • This is the complexity of Dijkstra’s algorithm. Vertex insertions and extractions from the priority queue occur at most \(N\) times, and edge relaxation occurs at most \(M\) times, each taking \(O(\log N)\).
• Space complexity: \(O(N + M)\)
  • Required for the graph’s adjacency list, the distance array, and the heap.

Implementation Notes

• sys.stdin.read is used for fast input reading.

• Elements are inserted into the heap in the form (distance, vertex), so that the vertex with the smallest distance is extracted first.

• Since the same vertex may be inserted into the queue multiple times, it is necessary to skip a vertex when it is extracted if its shortest distance has already been updated.

  Source Code

import heapq
import sys
from collections import defaultdict

input = sys.stdin.read

def main():
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    S = int(data[idx])
    idx += 1

    # グラフ構築
    graph = defaultdict(list)
    for _ in range(M):
        u = int(data[idx])
        idx += 1
        v = int(data[idx])
        idx += 1
        w = int(data[idx])
        idx += 1
        graph[u].append((v, w))
        graph[v].append((u, w))
    
    # ダイクストラ法
    dist = [float('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 graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    
    # 結果計算
    total = 0
    for i in range(1, N + 1):
        if i != S and dist[i] != float('inf'):
            total += dist[i]
    
    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.