概要

拠点間の道路ネットワークが与えられ、複数の配送依頼（拠点間の最短距離を求める）の合計を計算する問題です。

考察

\(N\) 件の配送依頼（\(S_i\) から \(T_i\) までの最短距離）の合計を求める問題ですが、\(N\) は最大 \(10^5\) と大きく、各依頼ごとに毎回最短経路を計算するのは非効率です。一方、拠点数 \(M\) は最大 \(200\) と小さいため、すべての拠点間の最短距離を事前に計算して保持しておく「全点対最短経路問題」として解くのが適切です。これにより、各依頼に対して事前計算した結果を \(O(1)\) で参照できるようになります。

アルゴリズム

ワーシャル–フロイド法を用いてすべての拠点間の最短距離を計算します。ワーシャル–フロイド法は、動的計画法を用いて、経由する拠点を順に考慮しながら最短距離を更新するアルゴリズムです。

1. 隣接行列 dist[i][j] を初期化します（同じ拠点は0、直接つながっている道路があればその距離、それ以外は十分大きな値）
2. 各拠点 \(k\) を経由する場合を考慮して、全拠点間の最短距離を更新します：
   • すべての \(i\), \(j\) について、dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) で更新
3. すべての配送依頼について、事前計算した dist[S_i][T_i] を合計します

計算量

• 時間計算量: \(O(M^3 + N)\)
  • ワーシャル–フロイド法の部分が \(O(M^3)\)
  • 配送依頼の処理が \(O(N)\)
• 空間計算量: \(O(M^2)\)
  • 拠点間の距離を保持する二次元配列が必要

実装のポイント

• 初期化時、同じ拠点間の距離は0に、直接つながっている道路の距離は最小値を取るように設定します（同じ拠点の組を結ぶ道路が複数ある場合はないですが、直接複数道路がある場合を想定）

• 十分大きな値（\(10^{18}\)）で初期化することで、到達不能な場合を表現します（ただし問題では到達可能が保証されています）

• 入力の読み込みには sys.stdin.read とイテレータを使用して効率化しています

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    N = int(next(it)); M = int(next(it)); K = int(next(it))
    
    graph = [[] for _ in range(M+1)]
    for _ in range(K):
        u = int(next(it)); v = int(next(it)); w = int(next(it))
        graph[u].append((v, w))
        graph[v].append((u, w))
    
    dist = [[10**18] * (M+1) for _ in range(M+1)]
    for i in range(1, M+1):
        dist[i][i] = 0
        
    for i in range(1, M+1):
        for neighbor, weight in graph[i]:
            dist[i][neighbor] = min(dist[i][neighbor], weight)
    
    for k in range(1, M+1):
        for i in range(1, M+1):
            if dist[i][k] == 10**18:
                continue
            for j in range(1, M+1):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    total = 0
    for _ in range(N):
        s = int(next(it)); t = int(next(it))
        total += dist[s][t]
    
    print(total)

if __name__ == "__main__":
    main()

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