概要

この問題は、拠点Sから他の全ての拠点への最短経路の移動コストを求め、それらの総和を計算するグラフ上の最短経路問題です。

考察

問題では、拠点Sから到達可能な全ての拠点vについて、最小の移動コストd(v)を求める必要があります。これは典型的な単一始点最短経路問題であり、効率的なアルゴリズムが必要です。

素朴なアプローチとして深さ優先探索や幅優先探索を考えられますが、辺の重みが正の値を持つため、単純なBFS/DFSでは最短経路を正しく求められません。また、ベルマンフォード法では計算量がO(N*M)となり、NとMが最大20万まで大きくなるため、時間制限に間に合いません。

この問題では、辺の重みが非負であるため、ダイクストラ法を用いることで効率的に解くことができます。

アルゴリズム

ダイクストラ法を使用して、拠点Sから他の全ての拠点への最短距離を計算します。具体的な手順は以下の通りです：

1. 各拠点への距離を無限大（INF）で初期化し、始点Sの距離を0に設定
2. 優先度付きキュー（最小ヒープ）を使用して、距離が最小の拠点から順に処理
3. 現在の拠点から隣接する拠点について、新しい経路の距離が現在の距離より小さい場合に更新
4. 全ての拠点を処理した後、S以外の到達可能な拠点の距離を合計

ダイクストラ法は、辺の重みが非負の場合に最短経路を正しく求めることができ、計算量も効率的です。

計算量

• 時間計算量: \(O((N + M) \log N)\)（優先度付きキューを用いたダイクストラ法の標準的な計算量）
• 空間計算量: \(O(N + M)\)（グラフの表現と距離配列に必要なメモリ）

実装のポイント

• 入力値が大きいため、sys.stdin.read()を使用して高速に入力処理

• 0-indexedで処理するために、入力された拠点番号から1を減算

• 距離の初期値として十分に大きな値（10^18）を使用

• 優先度付きキューから取り出した距離が現在の距離と異なる場合、スキップする処理を入れることで無駄な計算を回避

• 到達不可能な拠点（距離がINF）は合計に含めないように注意

  ソースコード

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

この解説は deepseekv3 によって生成されました。