最短路(Spfa)（信息学奥赛一本通- P1382）

【题目描述】

【输入】

【输出】

【输入样例】

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

【输出样例】

2

【提示】

0. 题目概要

给定N个点 (N<=10^5) 和M条边 (M<=5*10^5) 的带权无向图。

求从点 1 到点N的最短距离。

提示：虽然题目指定用 SPFA，但在实际工程或比赛中，对于正权图，堆优化 Dijkstra 是更稳定的选择。

1. 算法解析

1.1 SPFA 的核心逻辑

SPFA是 Bellman-Ford 的队列优化版。

• 核心思想：只有“变短了”的点，才有可能去更新它的邻居。

• 实现机制：

  1. 用队列维护所有“距离被更新且尚未处理”的节点。

  2. 取出队首节点u，取消标记。

  3. 遍历u的所有出边 (u, v, w)。

  4. 松弛操作：如果dis[v] > dis[u] + w，则更新dis[v]。

  5. 如果v更新了且不在队列中，将v入队并标记。

1.2 空间与时间

• 空间：由于是无向图，存图时需要建双向边，因此边数组的大小必须开到2*M。本题 M=500,000，数组至少要开1,000,000。

• 时间：SPFA 的平均时间复杂度是O(kM)(k为常数，约 2~4)。但在最坏情况下（如网格图）会退化为O(NM)。本题数据通常较弱，SPFA 可过。

2. 易错点

1. 数组越界：这是无向图最短路最容易挂的地方，M是 50 万，vtex,nxt,wt必须开到100 万以上。

2. IO 瓶颈：M很大，输入数据多，建议使用快读或关闭同步流ios::sync_with_stdio(false）; cin.tie(0);

3. 重边与自环：SPFA 的松弛操作if(dis[v] > dis[u] + w)天然能处理重边（会自动选短的那条）和自环（不会死循环），无需特殊处理。

3. 完整代码

//题目写了spfa 我们就spfa #include <iostream> #include <cstring> #include <queue> using namespace std; int n,m; const int maxn=100010; const int maxm=1100000; int h[maxn]; int vtex[maxm]; int nxt[maxm]; int wt[maxm]; int idx; int dis[maxn]; int is_used[maxn];//标记每个点是否在队列中 queue<int> q; void spfa(int s){ dis[s]=0;//起点到自己距离为0 int tmp=s; q.push(tmp);//起点入队 is_used[tmp]=1;//打上标记 while(!q.empty()){ tmp=q.front();//访问队首 q.pop();//出队 is_used[tmp]=0;//取消标记 int p=h[tmp];//tmp头指针 while(p!=-1){//遍历tmp所有邻接点 //如果该邻接点到源点距离大于 tmp到源点距离+边权 if(dis[vtex[p]]>dis[tmp]+wt[p]){ //就更新该邻接点到源点距离 dis[vtex[p]]=dis[tmp]+wt[p]; //如果该邻接点不在队中就入队并打上标记否则不用理会 if(is_used[vtex[p]]==0){ q.push(vtex[p]); is_used[vtex[p]]=1; } } p=nxt[p];//更新指针 } } } void addedge(int u,int v,int w){ vtex[idx]=v; nxt[idx]=h[u]; wt[idx]=w; h[u]=idx++; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n>>m; memset(h,-1,sizeof(h)); //邻接表存图 for(int i=1;i<=m;i++){ int a,b,c; cin>>a>>b>>c; addedge(a,b,c);//无向即双向路 addedge(b,a,c); } memset(dis,0x3f,sizeof(dis));//初始化所有点到1距离为无穷 spfa(1); cout<<dis[n]; return 0; }

4. 总结

这道题是 SPFA 的入门模板题。

• 优点：代码比堆优化 Dijkstra 短，逻辑简单，能处理负权边。

• 缺点：极其不稳定，容易被出题人卡tle。

• 策略：如果题目没明确说“可能有负权边”，尽量首选 Dijkstra。但本题指名道姓要 SPFA，那就用，数组开够即可。