概要

この問題は、\(M\) 個の拠点と \(K\) 本の道路からなるグラフにおいて、\(N\) 個の配送依頼（地点 \(S_i\) から \(T_i\) への移動）それぞれの最短距離を求め、その合計を算出する問題です。

考察

最短距離を求めるアルゴリズムには、ダイクストラ法やワーシャル・フロイド法などがあります。この問題の特徴は、「拠点の数 \(M\) が最大 200 と非常に小さい」一方で、「配送依頼の数 \(N\) が最大 \(10^5\) と非常に多い」点にあります。

なぜ素朴な方法ではいけないのか

各配送依頼（\(N\) 件）に対して、その都度ダイクストラ法などで最短経路を計算すると、計算量は \(O(N \times (K \log M))\) 程度になります。 \(N = 10^5, K = 2 \times 10^4\) の場合、計算回数は \(10^9\) を超えてしまい、実行時間制限（通常 2 秒程度）に間に合いません。

どう解決するか

\(M\) が小さいことに注目し、あらかじめ全拠点間の最短距離をすべて計算しておくアプローチをとります。 全拠点間の最短距離が分かっていれば、各配送依頼に対しては「拠点 \(S_i\) から \(T_i\) までの距離をテーブルから引く」だけで済むため、1 件あたり \(O(1)\) で回答できます。

全拠点間の最短距離を求めるには、ワーシャル・フロイド法が最適です。

アルゴリズム

ワーシャル・フロイド法

すべての拠点のペア \((i, j)\) について、最短距離を求めるアルゴリズムです。

1. 初期化:
   • \(M \times M\) の 2 次元配列 dist を用意し、すべて無限大（\(\text{INF}\)）で埋めます。
   • 自分の拠点への距離 dist[i][i] は \(0\) とします。
   • 与えられた道路の情報に基づき、道路がある地点間の距離を dist[u][v] と dist[v][u] に記録します。
2. 更新:
   • 3 重のループを使い、経由する拠点 \(k\)、始点 \(i\)、終点 \(j\) を順に回します。
   • 「\(i\) から \(j\) へ直接行く距離」と「\(k\) を経由して行く距離（\(i \to k \to j\)）」を比較し、小さい方で更新します。
   • 式: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

合計の算出

すべての依頼 \((S_i, T_i)\) について dist[S_i][T_i] を足し合わせれば答えとなります。

計算量

• 時間計算量: \(O(M^3 + N + K)\)
  • ワーシャル・フロイド法に \(O(M^3)\)、道路の読み込みに \(O(K)\)、配送依頼の処理に \(O(N)\) かかります。
  • \(M=200\) のとき \(M^3 = 8,000,000\) であり、Python でも十分に高速に動作します。
• 空間計算量: \(O(M^2)\)
  • 拠点間の距離を保持する \(M \times M\) の行列が必要です。

実装のポイント

• Python での高速化:

  • Python の 3 重ループは低速になりやすいため、内側のループでリストを直接参照する（di = dist[i] のようにローカル変数に置く）などの工夫をすると実行時間が短縮されます。
  • また、if dik == INF: continue のように、到達不可能な経路をスキップすることで無駄な計算を省いています。

• 大きな値（INF）の設定:

  • 最短距離が更新されない場合に備えて、十分大きな値を設定する必要があります。この問題では \(M \times \max(W_j)\) よりも大きい \(10^{15}\) などを使用します。

• 1-indexed から 0-indexed への変換:

  • 入力の拠点は \(1\) から \(M\) ですが、配列のインデックスとして使うために \(1\) を引いて \(0\) から \(M-1\) に変換して扱うとスムーズです。

    ソースコード

import sys

def solve():
    # Read all input at once for efficiency
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    if not input_data:
        return
    
    # Convert input data to integers
    data = list(map(int, input_data))
    
    N = data[0]
    M = data[1]
    K = data[2]
    
    # Initialize the distance matrix with a large value (infinity)
    # The maximum possible distance is roughly M * max(W) = 300 * 10^6 = 3 * 10^8
    INF = 10**15
    dist = [[INF] * M for _ in range(M)]
    for i in range(M):
        dist[i][i] = 0
        
    # Process each road and store the distance in the matrix
    # Roads are bidirectional, so we update both dist[u][v] and dist[v][u]
    idx = 3
    for _ in range(K):
        u = data[idx] - 1
        v = data[idx+1] - 1
        w = data[idx+2]
        if w < dist[u][v]:
            dist[u][v] = w
            dist[v][u] = w
        idx += 3
        
    # Floyd-Warshall algorithm to find all-pairs shortest paths
    # Time complexity: O(M^3), which is 300^3 = 27,000,000
    # This is slightly tight for Python but optimized with local variables
    for k in range(M):
        dk = dist[k]
        for i in range(M):
            di = dist[i]
            dik = di[k]
            # Optimization: If node i cannot reach node k, skip the inner loop
            if dik == INF:
                continue
            for j in range(M):
                # Check if the path from i to j through k is shorter than the current path
                new_dist = dik + dk[j]
                if di[j] > new_dist:
                    di[j] = new_dist
    
    # Sum the shortest distances for all N delivery requests
    total_shortest_distance = 0
    for _ in range(N):
        s = data[idx] - 1
        t = data[idx+1] - 1
        total_shortest_distance += dist[s][t]
        idx += 2
        
    # Output the total sum of shortest distances
    sys.stdout.write(str(total_shortest_distance) + '\n')

if __name__ == '__main__':
    solve()

---

この解説は gemini-3-flash-thinking によって生成されました。