P1339 Heat Wave G
网页链接
P1339 Heat Wave G
题目描述
有一个n nn个点m mm条边的无向图，请求出从s ss到t tt的最短路长度。
输入格式
第一行四个正整数n , m , s , t n,m,s,tn,m,s,t。
接下来m mm行，每行三个正整数u , v , w u,v,wu,v,w，表示一条连接u , v u,vu,v，长为w ww的边。
输出格式
输出一行一个整数，表示答案。
输入输出样例 #1
输入 #1
7 11 5 4 2 4 2 1 4 3 7 2 2 3 4 3 5 7 5 7 3 3 6 1 1 6 3 4 2 4 3 5 6 3 7 2 1输出 #1
7说明/提示
【数据范围】
对于100 % 100\%100%的数据，1 ≤ n ≤ 2500 1\le n \le 25001≤n≤2500，1 ≤ m ≤ 6200 1\le m \le 62001≤m≤6200，1 ≤ w ≤ 1000 1\le w \le 10001≤w≤1000。
【样例说明】
5 → 6 → 1 → 4 5 \to 6 \to 1 \to 45→6→1→4为最短路，长度为3 + 1 + 3 = 7 3+1+3 = 73+1+3=7。
解题思路
本题是经典的正权无向图单源最短路问题，采用堆优化 Dijkstra 算法求解。由于所有边权均为正整数，Dijkstra 算法可以稳定高效地计算起点到终点的最短路径。
采用链式前向星存储图结构，因为是无向图，每条边需双向添加。初始化距离数组为极大值，将起点距离设为 0，通过优先队列（以负距离模拟小顶堆）维护待处理节点，每次取出当前距离最短的节点。标记该节点已确定最短路后，遍历其所有邻边执行松弛操作：若经当前节点到达邻接点的路径更短，则更新邻接点距离并将其加入优先队列。算法时间复杂度为O ( m log n ) O(m\log n)O(mlogn)，完全适配题目数据范围。
总结
核心逻辑：基于贪心思想的 Dijkstra 算法，借助堆优化降低复杂度，逐步扩展最短路径集合。
关键操作：链式前向星建图、距离数组初始化、堆顶取点松弛邻边、更新最短距离。
效率保障：堆优化将朴素算法的平方级复杂度降至对数级，可快速处理千级节点与数千条边。
代码简要说明
- 图存储：使用链式前向星结构，
add函数为每条无向边添加正反两个方向的边，节省空间且遍历高效。 - 初始化：距离数组
d初始化为极大值，起点s距离置 0；访问标记数组v记录节点是否已确定最短路。 - 优先队列：存入
(-距离, 节点编号)，利用大顶堆特性模拟小顶堆，保证每次取出距离最小的节点。 - 松弛遍历：逐个取出堆顶节点，跳过已访问节点；遍历其所有邻边更新最短距离，更新后将新状态入队。最终输出终点
e的距离值。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;ll hea[620001],tot,d[600021],v[620001];ll n,m,s,e;priority_queue<pair<ll,ll>>q;structEdge{ll next,to,dis;}edge[620001];voidadd(ll x,ll y,ll z){edge[++tot].next=hea[x];edge[tot].to=y;edge[tot].dis=z;hea[x]=tot;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf("%lld%lld%lld%lld",&n,&m,&s,&e);for(ll i=1;i<=m;i++){ll x,y,z;scanf("%lld%lld%lld",&x,&y,&z);add(x,y,z);add(y,x,z);}memset(d,0x3f,sizeof(d));memset(v,0,sizeof(v));d[s]=0;q.push(make_pair(0,s));while(!q.empty()){ll x=q.top().second;q.pop();if(v[x])continue;v[x]=1;for(ll i=hea[x];i;i=edge[i].next){ll y=edge[i].to;if(d[y]>d[x]+edge[i].dis){d[y]=d[x]+edge[i].dis;q.push(make_pair(-d[y],y));}}}printf("%lld",d[e]);return0;}
