概要

道路で結ばれた拠点間について、\(N\) 個の配送依頼 \((S_i, T_i)\) それぞれの最短距離を求め、その合計を出力する問題です。

考察

• 求めたいのは「同じグラフ上で、たくさんの始点・終点ペアの最短距離」です。
  つまり クエリ（配送依頼）が \(N=10^5\) と非常に多い のがポイントです。
• 素朴に「依頼ごとにダイクストラ法」をすると、1回あたり \(O(K\log M)\) 程度かかります。これを \(10^5\) 回繰り返すと到底間に合いません。
• ここで拠点数 \(M \le 200\) が小さいことに注目します。
  全点対間最短距離（すべての \((u,v)\) の最短距離）を前計算してしまえば、各依頼は表から \(O(1)\) で取り出して足すだけになります。
• 全点対間最短距離の典型手法は ワーシャル–フロイド法 で、計算量は \(O(M^3)\)。
  \(M=200\) なら \(200^3=8,000,000\) 程度なので十分高速です。

（例）
拠点が少ないなら、先に「拠点1→拠点2の最短距離」「拠点1→拠点3の最短距離」…を全部埋めておき、配送依頼ごとに該当セルを見るだけ、というイメージです。

アルゴリズム

1. 距離行列 dist を用意する（サイズ \(M \times M\)）。
   • 初期値は \(\infty\)（十分大きい値）
   • dist[i][i] = 0
2. 各道路 \((U_j, V_j, W_j)\) について、
   • dist[U_j][V_j] = W_j, dist[V_j][U_j] = W_j（無向）
3. ワーシャル–フロイド法で全点対最短距離を計算する：
   • 中継点 \(k\) を 1 つずつ増やしながら
     dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) を全 \((i,j)\) に適用する。
4. 各配送依頼 \((S_i, T_i)\) について dist[S_i][T_i] を加算し、合計を出力する。

計算量

• 時間計算量: \(O(M^3 + N)\)
  （前計算が \(O(M^3)\)、各クエリの加算が \(O(1)\) なので合計 \(O(N)\)）
• 空間計算量: \(O(M^2)\)
  （距離行列 dist）

実装のポイント

• インデックスを 0-based に変換して扱う（入力は 1-based）。

• 距離の最大値は大きくなりうるため、\(\infty\) には 10**18 など十分大きい値を使う。

• ワーシャル–フロイド法では dist[i][k] が \(\infty\) のときに更新をスキップすると少し高速化できる（コード中の if aik == INF: continue）。

• 入力が大きいので sys.stdin.buffer.read() でまとめて読み、速度を確保する。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)
    K = next(it)

    INF = 10**18
    dist = [[INF] * M for _ in range(M)]
    for i in range(M):
        dist[i][i] = 0

    for _ in range(K):
        u = next(it) - 1
        v = next(it) - 1
        w = next(it)
        if w < dist[u][v]:
            dist[u][v] = w
            dist[v][u] = w

    for k in range(M):
        dk = dist[k]
        for i in range(M):
            di = dist[i]
            aik = di[k]
            if aik == INF:
                continue
            for j in range(M):
                nd = aik + dk[j]
                if nd < di[j]:
                    di[j] = nd

    ans = 0
    for _ in range(N):
        s = next(it) - 1
        t = next(it) - 1
        ans += dist[s][t]

    sys.stdout.write(str(ans))

if __name__ == "__main__":
    main()

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