概要

与えられた無向グラフにおいて、指定された始点 \(S\) から各頂点への最短距離を求め、それらの総和を出力する問題です。

考察

この問題は典型的な「単一始点最短経路問題」であり、始点 \(S\) から他のすべての頂点への最短距離を求める必要があります。
素朴な方法として、全経路を探索するような深さ優先探索や幅優先探索を試すことができますが、頂点数 \(N\) と辺数 \(M\) が最大 \(2 \times 10^5\) であるため、このような探索は計算量的に厳しく、時間内に解くことができません（TLE）。
また、辺に重みがあるため、単純な BFS では最短距離が求められないという問題もあります（WA）。

そこで、辺の重みが非負であることに注目し、「ダイクストラ法」を用いるのが適切です。ダイクストラ法は、優先度付きキューを用いることで効率的に最短経路を求めることができます。

さらに、到達できない頂点は無視して良いという条件があるので、最終的に \(d(v) \neq \infty\) である頂点だけを合計に加えるようにすればOKです。

アルゴリズム

1. グラフの構築: 隣接リスト形式で無向グラフを構築します。各辺は双方向に通ることができるので、両方向にエッジを追加します。
2. ダイクストラ法の適用:
   • 始点 \(S\) からの距離を管理する配列 dist を用意し、初期値はすべて \(\infty\)、\(S\) のみ \(0\) とします。
   • 優先度付きキュー（ヒープ）を用いて、現在の最も近い頂点を取り出し、隣接する頂点への距離を更新していきます。
3. 結果の集計: 頂点 \(1\) から \(N\) まで走査し、\(S\) 以外かつ到達可能な頂点（\(d(v) \neq \infty\)）の \(d(v)\) を合計します。

計算量

• 時間計算量: \(O((N + M) \log N)\)
  • ダイクストラ法の計算量。優先度付きキューによる頂点の挿入・取り出しが最大 \(N\) 回、辺の緩和処理が最大 \(M\) 回行われ、それぞれが \(\log N\) のオーダーです。
• 空間計算量: \(O(N + M)\)
  • グラフの隣接リストと距離配列、ヒープに必要な領域。

実装のポイント

• 入力を高速に読み込むために sys.stdin.read を使用しています。

• ヒープには (distance, vertex) の形で要素を入れることで、距離が最も小さい頂点から取り出せます。

• 同じ頂点が複数回キューに入る可能性があるため、取り出したときに既に最短距離が更新されている場合はスキップする処理が必要です。

  ソースコード

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()

この解説は qwen3-coder-480b によって生成されました。