题解：AtCoder AT_awc0089_d Cheapest Route

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderD - 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 PPM 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)(2k)-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)(K3)-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【代码详解】#includebits/stdc.husingnamespacestd;// 定义长整型别名便于处理大数据#defineintlonglong// 定义pair类型别名用于存储边权和对typedefpairint,intPII;// 小根堆优先队列用于Dijkstra算法priority_queuePII,vectorPII,greaterPIIpq;// 定义数组最大容量constintN200005,M200005;// 全局变量声明intn;// 节点数量intk;// 边的数量intp;// 目标节点数量intans1e18;// 记录最短距离初始化为极大值intm[N];// 每个节点的权值intdist[N];// 存储从起点到各节点的最短距离boolst[N];// 标记节点是否已确定最短距离vectorPIIh[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()){intupq.top().second;// 当前节点编号intwpq.top().first;// 当前距离pq.pop();// 如果该节点已经确定了最短距离跳过if(st[u]true)continue;// 标记该节点已确定最短距离st[u]true;dist[u]w;// 遍历当前节点的所有邻接节点for(inti0;ih[u].size();i){intvh[u][i].second;// 邻接节点编号intedge_wh[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(){// 读取节点数量、边的数量和目标节点数量cinnkp;// 读取每个节点的权值for(inti1;in;i)cinm[i];// 读取k条边并建图while(k--){intu,v;// 边的两个端点cinuv;intwm[u]*m[v];// 边权为两端点权值的乘积h[u].push_back({w,v});// 添加双向边h[v].push_back({w,u});}// 运行Dijkstra算法求最短路dijkstra();// 读取p个目标节点找出其中距离起点最近的那个for(inti1;ip;i){intx;// 目标节点编号cinx;ansmin(ans,dist[x]);// 更新最短距离}// 输出最短距离coutansendl;return0;}【运行结果】4 4 1 2 3 1 5 1 2 1 3 2 4 3 4 4 7