（信息学奥赛一本通- P1382）)
【题目描述】
给定 M 条边， N 个点的带权无向图。求 1到 N 的最短路。
【输入】
第一行：N,M(N<=100000，M<=500000)；
接下来M行3个正整数：ai,bi,ci表示ai,bi之间有一条长度为ci的路，ci<=1000。
【输出】
一个整数，表示 1 到 N 的最短距离。
【输入样例】
4 4 1 2 1 2 3 1 3 4 1 2 4 1【输出样例】
2【提示】
【样例解释】
注意图中可能有重边和自环,数据保证 1 到 N 有路径相连。
0. 题目概要
给定N个点 (N<=10^5) 和M条边 (M<=5*10^5) 的带权无向图。
求从点 1 到点N的最短距离。
提示：虽然题目指定用 SPFA，但在实际工程或比赛中，对于正权图，堆优化 Dijkstra 是更稳定的选择。
1. 算法解析
1.1 SPFA 的核心逻辑
SPFA是 Bellman-Ford 的队列优化版。
核心思想：只有“变短了”的点，才有可能去更新它的邻居。
实现机制：
用队列维护所有“距离被更新且尚未处理”的节点。
取出队首节点u，取消标记。
遍历u的所有出边 (u, v, w)。
松弛操作：如果
dis[v] > dis[u] + w，则更新dis[v]。如果v更新了且不在队列中，将v入队并标记。
1.2 空间与时间
空间：由于是无向图，存图时需要建双向边，因此边数组的大小必须开到2*M。本题 M=500,000，数组至少要开1,000,000。
时间：SPFA 的平均时间复杂度是O(kM)(k为常数，约 2~4)。但在最坏情况下（如网格图）会退化为O(NM)。本题数据通常较弱，SPFA 可过。
2. 易错点
数组越界：这是无向图最短路最容易挂的地方，M是 50 万，
vtex,nxt,wt必须开到100 万以上。IO 瓶颈：M很大，输入数据多，建议使用快读或关闭同步流
ios::sync_with_stdio(false）; cin.tie(0);重边与自环：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，那就用，数组开够即可。
