概要

都市 \(1\) から空港のあるいずれかの都市への最短経路を、ダイクストラ法を用いて求める問題です。辺のコストは両端の都市の人口の積で決まります。

考察

問題の言い換え

この問題は、重み付きグラフ上での最短経路問題に帰着できます。

• 頂点: \(N\) 個の都市
• 辺: \(K\) 本の道路。都市 \(a\) と都市 \(b\) を結ぶ辺の重みは \(M_a \times M_b\)
• 始点: 都市 \(1\)
• ゴール: 空港のある都市 \(E_1, E_2, \dots, E_P\) のいずれか

つまり、「都市 \(1\) から複数のゴール候補のうちどれか1つに最小コストで到達せよ」という単一始点最短経路問題です。

なぜダイクストラ法が使えるか

辺の重みは \(M_a \times M_b\) であり、\(M_i \geq 1\) なので全ての辺の重みは非負です。したがって、ダイクストラ法が正しく動作します。

素朴なアプローチとの比較

BFS（幅優先探索）は辺の重みが全て等しい場合にしか最短経路を求められません。本問では辺ごとに重みが異なるため、BFS では正しい答えが得られません（WA になります）。ダイクストラ法を使う必要があります。

ゴールが複数ある場合の処理

ダイクストラ法では、距離が小さい順に頂点を確定していきます。そのため、空港のある都市が初めてヒープから取り出された時点で、その距離が「いずれかの空港への最小コスト」となります。全ての空港までの距離を計算してから比較する必要はなく、最初に見つかった時点で打ち切れるのが効率的です。

アルゴリズム

1. グラフの構築: 各道路について、辺の重み \(M_{U_k} \times M_{V_k}\) を計算し、隣接リストに格納する。
2. 特殊ケースの処理: 都市 \(1\) 自体が空港のある都市なら、答えは \(0\)。
3. ダイクストラ法の実行:
   • 都市 \(1\) の距離を \(0\) に初期化し、優先度付きキュー（最小ヒープ）に入れる。
   • ヒープから最小距離の都市 \(u\) を取り出す。
   • \(u\) が空港のある都市であれば、その距離を出力して終了。
   • そうでなければ、\(u\) の隣接する都市 \(v\) について、\(dist[u] + M_u \times M_v\) が \(dist[v]\) を改善するならヒープに追加。
4. 最初に空港の都市がヒープから取り出された瞬間の距離が答え。

具体例

例えば、都市が3つ、道路が \((1,2)\) と \((2,3)\)、人口が \(M = [-, 3, 2, 5]\)（1-indexed）、空港が都市 \(3\) の場合：

• 辺 \((1,2)\) の重み: \(3 \times 2 = 6\)
• 辺 \((2,3)\) の重み: \(2 \times 5 = 10\)
• 都市 \(1 \to 2 \to 3\) のコスト: \(6 + 10 = 16\)

計算量

• 時間計算量: \(O((N + K) \log N)\)（ダイクストラ法の標準的な計算量）
• 空間計算量: \(O(N + K)\)（隣接リストと距離配列）

実装のポイント

• 早期終了: ヒープから取り出した都市が空港であれば即座に答えを出力して終了する。これにより、全頂点を探索せずに済む。

• 重複処理の回避: ヒープから取り出した距離 \(d\) が既に記録済みの \(dist[u]\) より大きい場合はスキップする（if d > dist[u]: continue）。これはダイクストラ法の定番テクニック。

• 高速入力: sys.stdin.buffer.read() を使って入力を一括読み込みすることで、Python でも TLE を回避しやすくなる。

• 空港の集合管理: 空港のある都市を set に格納することで、ある都市が空港かどうかを \(O(1)\) で判定できる。

  ソースコード

import heapq
import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    P = int(input_data[idx]); idx += 1
    
    M = [0] * (N + 1)
    for i in range(1, N + 1):
        M[i] = int(input_data[idx]); idx += 1
    
    adj = [[] for _ in range(N + 1)]
    for _ in range(K):
        u = int(input_data[idx]); idx += 1
        v = int(input_data[idx]); idx += 1
        cost = M[u] * M[v]
        adj[u].append((v, cost))
        adj[v].append((u, cost))
    
    airports = set()
    for _ in range(P):
        e = int(input_data[idx]); idx += 1
        airports.add(e)
    
    if 1 in airports:
        print(0)
        return
    
    INF = float('inf')
    dist = [INF] * (N + 1)
    dist[1] = 0
    heap = [(0, 1)]
    
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        if u in airports:
            print(d)
            return
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    
    # Should not reach here given the problem guarantees
    ans = INF
    for e in airports:
        ans = min(ans, dist[e])
    print(ans)

main()

---

この解説は claude4.6opus-thinking によって生成されました。