P1339 Heat Wave G
网页链接
P1339 Heat Wave G 
题目描述
有一个
n
n
n 个点
m
m
m 条边的无向图，请求出从
s
s
s 到
t
t
t 的最短路长度。
输入格式
第一行四个正整数
n
,
m
,
s
,
t
n,m,s,t
n,m,s,t。 接下来
m
m
m 行，每行三个正整数
u
,
v
,
w
u,v,w
u,v,w，表示一条连接
u
,
v
u,v
u,v，长为
w
w
w 的边。
输出格式
输出一行一个整数，表示答案。
输入输出样例 #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 2500
1≤n≤2500，
1
≤
m
≤
6200
1\\le m \\le 6200
1≤m≤6200，
1
≤
w
≤
1000
1\\le w \\le 1000
1≤w≤1000。
【样例说明】
5
→
6
→
1
→
4
5 \\to 6 \\to 1 \\to 4
5→6→1→4 为最短路，长度为
3
+
1
+
3
=
7
3+1+3 = 7
3+1+3=7。
解题思路
本题是经典的正权无向图单源最短路问题，采用堆优化 Dijkstra 算法求解。由于所有边权均为正整数，Dijkstra 算法可以稳定高效地计算起点到终点的最短路径。 采用链式前向星存储图结构，因为是无向图，每条边需双向添加。初始化距离数组为极大值，将起点距离设为 0，通过优先队列（以负距离模拟小顶堆）维护待处理节点，每次取出当前距离最短的节点。标记该节点已确定最短路后，遍历其所有邻边执行松弛操作：若经当前节点到达邻接点的路径更短，则更新邻接点距离并将其加入优先队列。算法时间复杂度为
O
(
m
log
n
)
O(m\\log n)
O(mlogn)，完全适配题目数据范围。
总结
核心逻辑：基于贪心思想的 Dijkstra 算法，借助堆优化降低复杂度，逐步扩展最短路径集合。 关键操作：链式前向星建图、距离数组初始化、堆顶取点松弛邻边、更新最短距离。 效率保障：堆优化将朴素算法的平方级复杂度降至对数级，可快速处理千级节点与数千条边。
代码简要说明
代码内容
#include <bits/stdc++.h>
using namespace std;
#define endl '\\n'
typedef long long ll;
typedef unsigned long long ull;
typedef vector<vector<ll>> vvt;
typedef pair<ll,ll> pll;
const ll N=1e3+10;
const ll INF=1e18;
const ll M=1e6+10;
const ll mod=1e9+7;
ll hea[620001],tot,d[600021],v[620001];
ll n,m,s,e;
priority_queue< pair<ll,ll> > q;
struct Edge{
ll next,to,dis;
}edge[620001];
void add(ll x,ll y,ll z)
{
edge[++tot].next=hea[x];
edge[tot].to=y;
edge[tot].dis=z;
hea[x]=tot;
}
int main()
{
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]);
return 0;
}
