概要

拠点 \(S\) から到達可能な各拠点への最短距離 \(d(v)\) をすべて求め、その総和 \(\sum d(v)\) を出力する問題です。重み付き無向グラフの 単一始点最短経路問題 に帰着します。

考察

• 求めたい \(d(v)\) は「拠点 \(S\) から拠点 \(v\) までの移動コストの最小値」＝ 最短距離です。
• 道路のコスト \(W_i\) はすべて正（\(1 \le W_i\)）なので、最短距離を求めるには ダイクストラ法が適用できます。

素朴な方法がダメな理由

• 各拠点 \(v\) について「全経路」を列挙して最小を取るのは不可能です。問題文では同じ拠点・道路を何回通ってもよいので、経路数は無限に増え得ます。
• BFSは辺の重みがすべて同じ（または \(0/1\)）でないと最短距離になりません。今回は重みが最大 \(10^4\) まで幅があるため、BFSではWAになります。
• ベルマン–フォード法は \(O(NM)\) で、最大 \(2\times 10^5\) 規模では間に合いません。

どう解決するか

• 「最短距離を効率よく全部求める」ためにダイクストラ法を使います。
• 到達不可能な拠点は距離が無限大のままになるので、最後に「\(S\) 以外で距離が確定したものだけ」合計します。

（例）
\(S \to A\) が \(5\)、\(S \to B\) が \(2\)、\(B \to A\) が \(1\) のとき、\(S \to A\) の最短は直接の \(5\) ではなく \(S\to B\to A\) の \(3\) になります。重みがあるため、単純に「辺数が少ない経路」が最短とは限りません。

アルゴリズム

1. グラフを隣接リストで保持する（無向なので両方向に追加）。
2. 距離配列 dist を用意し、dist[S]=0、それ以外は十分大きい値（INF）で初期化。
3. 優先度付きキュー（最小ヒープ）に (0, S) を入れる。
4. ヒープから「現在最も距離が小さい頂点」を取り出し、その距離が最新（d == dist[u]）なら採用し、隣接辺で緩和（relax）する：
   • 辺 \((u,v)\) のコストが \(w\) のとき、nd = dist[u] + w
   • nd < dist[v] なら dist[v]=nd に更新し、ヒープに追加
5. 全処理後、\(v \ne S\) かつ dist[v] < INF のものだけを合計して出力。

ダイクストラ法は「正の重み」のとき、ヒープから取り出した距離は最短距離として確定する、という性質を利用しています。

計算量

• 時間計算量: \(O((N+M)\log N)\)
  （各辺の緩和でヒープ操作が起きうるため）
• 空間計算量: \(O(N+M)\)
  （隣接リストと距離配列、ヒープ）

実装のポイント

• 到達不可能な頂点の扱い：dist が INF のままの頂点は合計に入れません。

• ヒープから取り出した要素の捨て処理：if d != dist[u]: continue を入れることで、古い距離情報（更新前に入ったゴミ）を無視できます。

• 入力が最大 \(2\times 10^5\) と大きいので、コードでは sys.stdin.buffer.read() を使った高速入力にしています。

  ソースコード

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)

この解説は gpt-5.2-high によって生成されました。