Overview

This is a problem of finding the route that minimizes the total toll when traveling between cities, and computing the minimum cost from city \(1\) to any city that has an airport.

Analysis

This problem can be thought of as a shortest path problem on a graph where cities are vertices and roads are edges. However, unlike a typical weighted graph, the weight (toll) of each edge is the product of the populations of the two cities \(M_u \times M_v\).

A naive approach would be to explore all possible routes to find the minimum cost, but since the number of cities \(N\) can be up to \(2 \times 10^5\), this is not practical. Therefore, we consider using Dijkstra’s algorithm, an efficient shortest path algorithm.

To apply Dijkstra’s algorithm, each edge weight must be non-negative. In this problem, since the population \(M_i \geq 1\), the toll \(M_u \times M_v \geq 1\), so this condition is satisfied.

Another key point is that there are multiple goals (multiple cities with airports). However, since the cost is minimized at the moment we first reach a city with an airport during Dijkstra’s algorithm, we can terminate the process at that point.

Algorithm

1. Read the array \(M\) storing the population of each city.
2. Build an undirected graph based on the road information. At this time, the weight of each edge is set to \(M_u \times M_v\).
3. Manage the cities with airports using a set.
4. Use Dijkstra’s algorithm to find the shortest distance from city \(1\).
   • Use a priority queue (heap) to explore vertices in order of increasing cost.
   • When visiting each vertex, if it is a city with an airport, the cost at that point is the answer.
5. Output the result and terminate as soon as we first reach a city with an airport.

Complexity

• Time complexity: \(O((N + K) \log N)\)
  • This is the time complexity of Dijkstra’s algorithm. Each vertex and edge is processed, and priority queue operations cost \(\log N\).
• Space complexity: \(O(N + K)\)
  • Memory used for the graph’s adjacency list, distance array, queue, etc.

Implementation Notes

• A key point is to pre-compute the edge weights and store them in the graph. Computing them each time would be inefficient.

• In the implementation of Dijkstra’s algorithm, it is necessary to avoid reprocessing vertices whose shortest distances have already been finalized.

• By immediately outputting the result and terminating as soon as we first reach a city with an airport, unnecessary computation can be avoided.

  Source Code

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()

---

This editorial was generated by qwen3-coder-480b.