概要

都市間を移動する際に通行料がかかる条件下で、都市1からいずれかの空港都市までの最小通行料を求める問題です。

考察

通行料は隣接する都市間の移動ごとに「出発都市の人口 × 到着都市の人口」として計算されます。この問題は、都市1から空港都市までの最短経路（最小通行料）を求めるグラフ問題と捉えることができます。

素朴なアプローチとして全探索が考えられますが、制約が大きい（N, K ≤ 2×10⁵）ため、ダイクストラ法などの効率的な最短経路アルゴリズムを使用する必要があります。通行料が非負の値（人口は正の整数）のみであるため、ダイクストラ法が適用可能です。

アルゴリズム

ダイクストラ法を用いて、都市1を始点とするすべての都市への最小通行料を計算します。優先度付きキューを使用して、未確定の都市の中から最小の通行料を持つ都市を順次確定させていきます。空港都市のいずれかに到達した時点で、その時点の通行料を出力して終了します（空港都市に到達したら出国できるため）。

具体的な手順： 1. 各都市への最小通行料を無限大で初期化し、都市1の通行料を0に設定 2. 優先度付きキューに(0, 1)を追加 3. キューが空になるまで以下を繰り返す： - 最小通行料の都市を取り出す - その都市が空港都市なら結果を出力して終了 - 隣接都市に対して、現在の通行料＋辺の通行料を計算し、より小さい値なら更新

計算量

• 時間計算量: \(O((N + K) \log N)\)
• 空間計算量: \(O(N + K)\)

実装のポイント

• 大規模な入力に対応するため、sys.stdin.read()で一括読み込みを行い、イテレータで処理

• 無限大の値として十分に大きい値（\(10^{18}\)）を使用

• グラフを隣接リストで表現し、各辺に通行料を保存

• 空港都市は集合で管理し、効率的な存在確認を実現

• 優先度付きキュー（ヒープ）を使用して、最小通行料の都市を効率的に取得

  ソースコード

import heapq
import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    it = iter(data)
    N = int(next(it)); K = int(next(it)); P = int(next(it))
    M = [0] * (N+1)
    for i in range(1, N+1):
        M[i] = int(next(it))
    
    graph = [[] for _ in range(N+1)]
    for _ in range(K):
        u = int(next(it)); v = int(next(it))
        cost_uv = M[u] * M[v]
        cost_vu = cost_uv
        graph[u].append((v, cost_uv))
        graph[v].append((u, cost_vu))
        
    airports = set()
    for _ in range(P):
        e = int(next(it))
        airports.add(e)
        
    INF = 10**18
    dist = [INF] * (N+1)
    dist[1] = 0
    heap = [(0, 1)]
    
    while heap:
        d, node = heapq.heappop(heap)
        if d != dist[node]:
            continue
        if node in airports:
            print(d)
            return
            
        for neighbor, cost in graph[node]:
            new_d = d + cost
            if new_d < dist[neighbor]:
                dist[neighbor] = new_d
                heapq.heappush(heap, (new_d, neighbor))
                
    ans = INF
    for a in airports:
        if dist[a] < ans:
            ans = dist[a]
    print(ans)

if __name__ == "__main__":
    main()

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