概要

各道路の移動コストが「両端都市の人口の積 \(M_a \times M_b\)」で与えられるグラフ上で、都市 \(1\) からいずれかの空港都市までの最小通行料（最短距離）を求める問題です。

考察

• 都市を頂点、道路を辺とみなすと、都市 \(a\) から隣接都市 \(b\) へ移動するコストは辺の重み \(w(a,b)=M_a \times M_b\) です。道路は双方向なので無向グラフですが、コストはどちら向きでも同じ（積なので対称）です。
• 求めたいのは「都市 \(1\) から、空港都市集合 \(\{E_1,\dots,E_P\}\) のどれかに到達するまでの最小コスト」＝「始点から複数の終点のうち最短のもの」です。

素朴案がダメな理由

• 全経路を探索（DFSで全パス列挙など）すると、同じ都市・道路を何度でも通れるため経路数が爆発します。
• BFSは辺重みがすべて同じときしか最短距離を保証できません。本問題では \(M_a \times M_b\) が辺ごとに異なり得るため、BFSでは誤答になります。

解決の方針

• 辺重みがすべて非負（\(M_i \ge 1\) なので積も正）なので、ダイクストラ法で最短距離を求められます。
• 終点が複数ある場合でも、ダイクストラ法で「最短距離が確定した頂点」を順に取り出していく性質を使えば、空港都市を最初に確定した時点でそれが答えになります（それより安い空港は存在しない）。

例：空港が複数あっても、優先度付きキューから取り出される距離は単調増加なので、「最初に取り出された空港」は全空港の中で最小距離です。

アルゴリズム

1. 空港都市かどうかを配列 is_airport で管理する。
2. もし都市 \(1\) が空港なら、移動不要で答えは \(0\)。
3. 距離配列 dist を用意し、dist[1]=0、それ以外は \(\infty\)。
4. 優先度付きキュー（最小ヒープ）に (0, 1) を入れてダイクストラ法を開始。
5. ヒープから (d, u) を取り出す。
   • 取り出した d が dist[u] と違うなら古い情報なので無視。
   • もし u が空港都市なら、d が最小通行料なので出力して終了。
6. u の全隣接頂点 v について、遷移コスト \(M_u \times M_v\) を加えた $\( nd = d + M_u \times M_v \)$ で緩和し、nd < dist[v] なら更新してヒープへ入れる。
7. 必ずどれかの空港へ到達可能なので、どこかで終了する。

計算量

• 時間計算量: \(O((N+K)\log N)\)
  （ダイクストラ法：各辺の緩和が最大 \(2K\) 回、ヒープ操作が \(\log N\)）
• 空間計算量: \(O(N+K)\)
  （隣接リスト、距離配列、空港フラグ、ヒープ）

実装のポイント

• 「空港に着いたら即終了」が重要です。ダイクストラ法では最小距離の頂点から確定していくため、最初に確定した空港が答えになります。

• Pythonでは入力が大きいので、sys.stdin.buffer.read() を使った高速入力にしています。

• 隣接リストも head/to/nxt の配列形式（C言語風）にして、\(N,K \le 2\times 10^5\) でも高速に走るようにしています。

• 距離の最大値は大きくなり得るため（経路長により積が多数回加算）、INF=10**30 のように十分大きい値を使います。

  ソースコード

import sys
import heapq

def main():
    data = sys.stdin.buffer.read()
    ndata = len(data)
    ptr = 0

    def next_int():
        nonlocal ptr
        while ptr < ndata and data[ptr] <= 32:
            ptr += 1
        sign = 1
        if ptr < ndata and data[ptr] == 45:
            sign = -1
            ptr += 1
        num = 0
        while ptr < ndata:
            c = data[ptr]
            if c <= 32:
                break
            num = num * 10 + (c - 48)
            ptr += 1
        return num * sign

    N = next_int()
    K = next_int()
    P = next_int()

    M = [0] * (N + 1)
    for i in range(1, N + 1):
        M[i] = next_int()

    head = [-1] * (N + 1)
    to = [0] * (2 * K)
    nxt = [0] * (2 * K)
    ei = 0
    for _ in range(K):
        u = next_int()
        v = next_int()
        to[ei] = v
        nxt[ei] = head[u]
        head[u] = ei
        ei += 1
        to[ei] = u
        nxt[ei] = head[v]
        head[v] = ei
        ei += 1

    is_airport = [False] * (N + 1)
    for _ in range(P):
        e = next_int()
        is_airport[e] = True

    if is_airport[1]:
        print(0)
        return

    INF = 10**30
    dist = [INF] * (N + 1)
    dist[1] = 0
    hq = [(0, 1)]

    while hq:
        d, u = heapq.heappop(hq)
        if d != dist[u]:
            continue
        if is_airport[u]:
            print(d)
            return
        mu = M[u]
        e = head[u]
        while e != -1:
            v = to[e]
            nd = d + mu * M[v]
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(hq, (nd, v))
            e = nxt[e]

if __name__ == "__main__":
    main()

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