题解：AtCoder AT_awc0089_d Cheapest Route

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

AtCoder：D - Cheapest Route

【题目描述】

Takahashi lives in a country consisting ofN NNcities. Each city is numbered from1 11toN NN, and the population of cityi iiisM i M_iMi​.

There areK KKroads in this country, and roadk kkbidirectionally connects cityU k U_kUk​and cityV k V_kVk​. Takahashi can travel in either direction between two cities that are directly connected by a road. He may also pass through the same road or the same city multiple times.

Each time Takahashi travels from citya aato an adjacent cityb bbthat is directly connected by a road, he must pay a toll ofM a × M b M_a \times M_bMa​×Mb​.

Takahashi is currently in city1 11. There areP PPcities with airports in this country, which are citiesE 1 , E 2 , … , E P E_1, E_2, \dots, E_PE1​,E2​,…,EP​. Takahashi can leave the country once he reaches any city with an airport. If city1 11itself has an airport, he can leave without moving, and the total toll is0 00.

Find the minimum total toll Takahashi must pay to travel from city1 11to any city with an airport. It is guaranteed that at least one city with an airport is reachable from city1 11.

高桥住在一个有N NN个城市组成的国家。每个城市编号从1 11到N NN，城市i ii的人口为M i M_iMi​。

这个国家有K KK条道路，道路k kk双向连接城市U k U_kUk​和城市V k V_kVk​。高桥可以在由道路直接连接的两个城市之间双向移动。他也可以多次经过同一条道路或同一个城市。

每次高桥从一个城市a aa移动到由道路直接连接的相邻城市b bb时，他必须支付M a × M b M_a \times M_bMa​×Mb​的通行费。

高桥目前在1 11号城市。这个国家有P PP个有机场的城市，分别是E 1 , E 2 , … , E P E_1, E_2, \dots, E_PE1​,E2​,…,EP​。一旦高桥到达任何一个有机场的城市，他就可以离开这个国家。如果1 11号城市本身就有机场，他可以不移动就离开，总通行费为0 00。

求高桥从1 11号城市到达任意一个有机场的城市所需支付的最小总通行费。保证至少有一个有机场的城市可以从1 11号城市到达。

【输入】

N NNK KKP PP
M 1 M_1M1​M 2 M_2M2​… \dots…M N M_NMN​
U 1 U_1U1​V 1 V_1V1​
U 2 U_2U2​V 2 V_2V2​
⋮ \vdots⋮
U K U_KUK​V K V_KVK​
E 1 E_1E1​E 2 E_2E2​… \dots…E P E_PEP​

• The first line contains the number of citiesN NN, the number of roadsK KK, and the number of cities with airportsP PP, separated by spaces.
• The second line contains the population of each cityM 1 , M 2 , … , M N M_1, M_2, \dots, M_NM1​,M2​,…,MN​, separated by spaces.
• The followingK KKlines provide information about the roads.
• The( 2 + k ) (2 + k)(2+k)-th line( 1 ≤ k ≤ K ) (1 \leq k \leq K)(1≤k≤K)contains the numbers of the two cities connected by roadk kk,U k U_kUk​andV k V_kVk​, separated by spaces.
• The( K + 3 ) (K + 3)(K+3)-th line contains the numbers of the cities with airportsE 1 , E 2 , … , E P E_1, E_2, \dots, E_PE1​,E2​,…,EP​, separated by spaces.

【输出】

Print in one line the minimum total toll Takahashi must pay to travel from city1 11to any city with an airport.

【输入样例】

4 4 1 2 3 1 5 1 2 1 3 2 4 3 4 4

【输出样例】

7

【算法标签】

#Dijkstra

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;// 定义长整型别名，便于处理大数据#defineintlonglong// 定义pair类型别名，用于存储边权和对typedefpair<int,int>PII;// 小根堆优先队列，用于Dijkstra算法priority_queue<PII,vector<PII>,greater<PII>>pq;// 定义数组最大容量constintN=200005,M=200005;// 全局变量声明intn;// 节点数量intk;// 边的数量intp;// 目标节点数量intans=1e18;// 记录最短距离，初始化为极大值intm[N];// 每个节点的权值intdist[N];// 存储从起点到各节点的最短距离boolst[N];// 标记节点是否已确定最短距离vector<PII>h[N];// 邻接表，存储图的边信息inte[N];// 未使用的数组（保留原样）// Dijkstra求最短路算法voiddijkstra(){// 初始化标记数组和距离数组memset(st,0,sizeof(st));memset(dist,0x3f,sizeof(dist));// 起点为节点1，距离为0pq.push({0,1});dist[1]=0;// 主循环：每次取出距离最小的未确定节点while(!pq.empty()){intu=pq.top().second;// 当前节点编号intw=pq.top().first;// 当前距离pq.pop();// 如果该节点已经确定了最短距离，跳过if(st[u]==true)continue;// 标记该节点已确定最短距离st[u]=true;dist[u]=w;// 遍历当前节点的所有邻接节点for(inti=0;i<h[u].size();i++){intv=h[u][i].second;// 邻接节点编号intedge_w=h[u][i].first;// 边权// 松弛操作：如果经过u到达v的距离更短，则更新if(dist[v]>dist[u]+edge_w){dist[v]=dist[u]+edge_w;pq.push({dist[v],v});// 将新的距离加入优先队列}}}}// 主函数入口（使用signed避免与long long冲突）signedmain(){// 读取节点数量、边的数量和目标节点数量cin>>n>>k>>p;// 读取每个节点的权值for(inti=1;i<=n;i++)cin>>m[i];// 读取k条边并建图while(k--){intu,v;// 边的两个端点cin>>u>>v;intw=m[u]*m[v];// 边权为两端点权值的乘积h[u].push_back({w,v});// 添加双向边h[v].push_back({w,u});}// 运行Dijkstra算法求最短路dijkstra();// 读取p个目标节点，找出其中距离起点最近的那个for(inti=1;i<=p;i++){intx;// 目标节点编号cin>>x;ans=min(ans,dist[x]);// 更新最短距离}// 输出最短距离cout<<ans<<endl;return0;}

【运行结果】

4 4 1 2 3 1 5 1 2 1 3 2 4 3 4 4 7