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输入 #17 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输出 #17说明/提示【数据范围】对于100 % 100\%100%的数据1 ≤ n ≤ 2500 1\le n \le 25001≤n≤25001 ≤ m ≤ 6200 1\le m \le 62001≤m≤62001 ≤ 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 313 73137。解题思路本题是经典的正权无向图单源最短路问题采用堆优化 Dijkstra 算法求解。由于所有边权均为正整数Dijkstra 算法可以稳定高效地计算起点到终点的最短路径。采用链式前向星存储图结构因为是无向图每条边需双向添加。初始化距离数组为极大值将起点距离设为 0通过优先队列以负距离模拟小顶堆维护待处理节点每次取出当前距离最短的节点。标记该节点已确定最短路后遍历其所有邻边执行松弛操作若经当前节点到达邻接点的路径更短则更新邻接点距离并将其加入优先队列。算法时间复杂度为O ( m log ⁡ n ) O(m\log n)O(mlogn)完全适配题目数据范围。总结核心逻辑基于贪心思想的 Dijkstra 算法借助堆优化降低复杂度逐步扩展最短路径集合。关键操作链式前向星建图、距离数组初始化、堆顶取点松弛邻边、更新最短距离。效率保障堆优化将朴素算法的平方级复杂度降至对数级可快速处理千级节点与数千条边。代码简要说明图存储使用链式前向星结构add函数为每条无向边添加正反两个方向的边节省空间且遍历高效。初始化距离数组d初始化为极大值起点s距离置 0访问标记数组v记录节点是否已确定最短路。优先队列存入(-距离, 节点编号)利用大顶堆特性模拟小顶堆保证每次取出距离最小的节点。松弛遍历逐个取出堆顶节点跳过已访问节点遍历其所有邻边更新最短距离更新后将新状态入队。最终输出终点e的距离值。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll hea[620001],tot,d[600021],v[620001];ll n,m,s,e;priority_queuepairll,llq;structEdge{ll next,to,dis;}edge[620001];voidadd(ll x,ll y,ll z){edge[tot].nexthea[x];edge[tot].toy;edge[tot].disz;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 i1;im;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 xq.top().second;q.pop();if(v[x])continue;v[x]1;for(ll ihea[x];i;iedge[i].next){ll yedge[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;}