概要

都市間を移動する際にかかる通行料の合計が最小となる経路を見つけ、都市 \(1\) からいずれかの空港のある都市への最短コストを求める問題です。

考察

この問題は、都市を頂点、道路を辺としたグラフ上の最短経路問題と考えることができます。ただし、通常の重み付きグラフと異なり、辺の重み（通行料）は移動する2つの都市の人口の積 \(M_u \times M_v\) となっています。

素朴な方法として、すべての経路を探索して最小コストを求める方法がありますが、都市数 \(N\) は最大 \(2 \times 10^5\) であり、現実的ではありません。そこで、効率的な最短経路探索アルゴリズムであるダイクストラ法を用いることを考えます。

ダイクストラ法を適用するためには、各辺の重みが非負である必要があります。今回の問題では、人口 \(M_i \geq 1\) なので、通行料 \(M_u \times M_v \geq 1\) となり、条件を満たしています。

また、ゴールが複数ある（空港のある都市が複数）という点もポイントですが、ダイクストラ法の途中で最初に空港のある都市に到達した時点でそのコストが最小となるため、そこで処理を終えることができます。

アルゴリズム

1. 各都市の人口を格納する配列 \(M\) を読み込みます。
2. 道路の情報を元に、無向グラフを構築します。このとき、各辺の重みは \(M_u \times M_v\) とします。
3. 空港のある都市を集合（set）で管理します。
4. ダイクストラ法を用いて、都市 \(1\) からの最短距離を求めます。
   • 優先度付きキュー（ヒープ）を使用して、最もコストの小さい頂点から探索を進めます。
   • 各頂点を訪問する際に、それが空港のある都市であれば、その時点でのコストが答えとなります。
5. 最初に空港のある都市に到達した時点で結果を出力して終了します。

計算量

• 時間計算量: \(O((N + K) \log N)\)
  • ダイクストラ法の時間計算量です。各頂点と辺について処理を行い、優先度付きキューによる操作が \(\log N\) かかります。
• 空間計算量: \(O(N + K)\)
  • グラフの隣接リスト、距離配列、キューなどで使用されるメモリです。

実装のポイント

• 辺の重みを事前に計算してグラフに持たせるのがポイントです。毎回計算すると非効率です。

• ダイクストラ法の実装では、すでに最短距離が確定している頂点を再度処理しないようにする必要があります。

• 空港のある都市に最初に到達した時点で即座に出力して終了することで、不要な計算を省略できます。

  ソースコード

import heapq
import sys

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    P = int(data[idx]); idx += 1
    
    M = [0] * (N + 1)
    for i in range(1, N + 1):
        M[i] = int(data[idx]); idx += 1
    
    # グラフ構築
    graph = [[] for _ in range(N + 1)]
    for _ in range(K):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        cost = M[u] * M[v]
        graph[u].append((v, cost))
        graph[v].append((u, cost))
    
    # 空港がある都市
    airports = set()
    for _ in range(P):
        e = int(data[idx]); idx += 1
        airports.add(e)
    
    # ダイクストラ法
    dist = [float('inf')] * (N + 1)
    dist[1] = 0
    pq = [(0, 1)]
    
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        # 空港に到達したら終了
        if u in airports:
            print(d)
            return
        for v, cost in graph[u]:
            new_dist = d + cost
            if new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(pq, (new_dist, v))

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。