（信息学奥赛一本通- P1381）)
【题目描述】
罗老师被邀请参加一个舞会，是在城市n，而罗老师当前所处的城市为1,附近还有很多城市2∼n−1，有些城市之间没有直接相连的路，有些城市之间有直接相连的路，这些路都是双向的，当然也可能有多条。
现在给出直接相邻城市的路长度，罗老师想知道从城市1到城市n，最短多少距离。
【输入】
输入n, m，表示n个城市和m条路;
接下来m行，每行abc， 表示城市a与城市b有长度为c的路。
【输出】
输出1到n的最短路。如果1到达不了n，就输出−1。
【输入样例】
5 5 1 2 20 2 3 30 3 4 20 4 5 20 1 5 100【输出样例】
90【提示】
【数据规模和约定】
1≤n≤2000
1≤m≤10000
0≤c≤10000
0. 题目速览
题意：给定N个点M条边的无向正权图，求点1到点N的最短距离。不可达输出 -1。
数据：N<=2000，M<=10000。
1. 核心难点与算法选型
做题时，首先分析数据量，面对N=2000的数据，选择错误的算法直接导致tle
| 算法 | 复杂度 | 计算量预估 | 判决 | 评价 |
| Floyd | O(N^3) | 8*10^9 | 必挂 | 只能跑N<=300。80亿次运算需要几十秒。 |
| Bellman-Ford | O(N*M) | 4*10^7 | 勉强过 | 效率一般，若N再大一点就会超时。 |
| SPFA | Avg O(k* M) | 约2*10^5 | AC | 平均极快，但最坏情况退化为O(N*M)。正权图不建议作为首选。 |
| Dijkstra (堆优化) | O(M log N) | 约 2*10^5 | 完美 AC | 正权图首选，最稳定，无视数据构造。 |
结论：本题最佳方案为Dijkstra（堆优化）。
2. 易错点
无向图陷阱：
题目是双向路，存图时必须建两条边：
addedge(u, v, w)和addedge(v, u, w)。如果是邻接矩阵（Floyd），记得
g[u][v] = g[v][u] = min(...)。
头文件：
使用
memset建议加<cstring>。使用
min/max建议加<algorithm>。注：这是比赛中最常见的 CE 原因。
不可达判断：
初始化
dis为INF(如0x3f3f3f3f)。输出前检查
if (dis[n] == 0x3f3f3f3f) cout << -1;。
3. 完整代码
//n是2*10^3量级，此题最佳还是Dijkstra 但我也写个spfa和floyd做个示范 /* //第一种 Dijkstra #include <iostream> #include <queue> #include <cstring> using namespace std; const int maxn=2100; const int maxm=21000; int n,m; int h[maxn]; int vtex[maxm]; int nxt[maxm]; int wt[maxm]; int idx; int dis[maxn];//每个城市到1号城市到最短距离 int vis[maxn]; struct node{ int id;//每个城市编号 int w;//每个城市到一号城市的最短距离 //优先队列默认大根堆，重载运算符变为小根堆 friend bool operator <(node a,node b){ return a.w>b.w; } }; priority_queue<node> q; void dijkstra(int s){ dis[s]=0;//起点到自己距离为0 node tmp; tmp.id=s; tmp.w=0;//记录这个才能确保每次出队都是离1号城市距离最近的城市 q.push(tmp);//源点入队 while(!q.empty()){ tmp=q.top();//访问队首元素 q.pop();//队首出队 int nid=tmp.id;//当前出队城市编号 if(vis[nid]==1) continue;//如果tmp已经出队过，就直接跳过 vis[nid]=1;//否则就打上出队标记 int p=h[nid];//记录tmp头指针 while(p!=-1){//遍历tmp所有邻接点 if(vis[vtex[p]]==0){//如果该邻接点没有出队过 //如果该邻接点到1号城市距离大于 tmp到1号城市距离+边权 //就更新该邻接点到1号城市距离并入队 if(dis[vtex[p]]>dis[nid]+wt[p]){ dis[vtex[p]]=dis[nid]+wt[p]; q.push({vtex[p],dis[vtex[p]]}); } } 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(){ cin>>n>>m; memset(h,-1,sizeof(h));//初始化头指针数组 //邻接表存图 for(int i=1;i<=m;i++){ int u,v,w; cin>>u>>v>>w; addedge(u,v,w);//双向道路 addedge(v,u,w); } for(int i=1;i<=n;i++) dis[i]=0x3f3f3f3f;//初始化最短距离为无穷 dijkstra(1); if(dis[n]==0x3f3f3f3f) cout<<-1; else cout<<dis[n]; return 0; } */ /* //floyd #include <iostream> #include <cstring> #include <algorithm> using namespace std; int n,m; int g[2100][2100]; void floyd(){ for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ g[i][j]=min(g[i][j],g[i][k]+g[k][j]); } } } } int main(){ cin>>n>>m; //初始化邻接矩阵内所有城市间距离为无穷 for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ g[i][j]=0x3f3f3f3f; } } for(int i=1;i<=n;i++) g[i][i]=0;//所有城市自己到自己距离为0； //邻接矩阵存图 for(int i=1;i<=m;i++){ int u,v,w; cin>>u>>v>>w; //防止两个城市间有多条重复边，但是边距离不同 g[u][v]=g[v][u]=min(g[u][v],w); } floyd(); if(g[1][n]==0x3f3f3f3f) cout<<-1; else cout<<g[1][n]; return 0; } */ /* //spfa #include <iostream> #include <cstring> #include <queue> using namespace std; queue<int> q; const int maxn=2100; const int maxm=21000; int n,m; int h[maxn]; int vtex[maxm]; int nxt[maxm]; int wt[maxm]; int idx; int dis[maxn];//每个城市到1号城市到最短距离 bool is_used[maxn];//记录每个城市是否在队列中 void spfa(int s){ int tmp=s; dis[tmp]=0;//源点到自己距离为0 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){ is_used[vtex[p]]=1; q.push(vtex[p]); } } 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(){ cin>>n>>m; memset(h,-1,sizeof(h));//初始化头指针数组 //邻接表存图 for(int i=1;i<=m;i++){ int u,v,w; cin>>u>>v>>w; addedge(u,v,w);//双向道路 addedge(v,u,w); } for(int i=1;i<=n;i++) dis[i]=0x3f3f3f3f;//初始化所有点到dis的距离为无穷 spfa(1); if(dis[n]==0x3f3f3f3f) cout<<-1; else cout<<dis[n]; return 0; } */ //bellman-ford #include <iostream> using namespace std; int n,m; struct edge{ int u; int v; int w; }e[21000];//存所有边 int dis[2100]; void ford(int s){ dis[s]=0;//起点到自己距离为0 for(int i=1;i<n;i++){//迭代n-1次 bool flag=0;//标记这一整轮是否发生更新 for(int j=1;j<=2*m;j++){//双向道路，所以是2*m条 //如果一条边终点到源点距离大于 边起点到源点距离+边权 就更新边终点到源点距离 if(dis[e[j].v]>dis[e[j].u]+e[j].w){ dis[e[j].v]=dis[e[j].u]+e[j].w; flag=1;//并更新标记 } } if(flag==0) break;//当一整轮都没有发生更新，就退出 } } int main(){ cin>>n>>m; for(int i=1;i<=n;i++) dis[i]=0x3f3f3f3f;//初始化每个点到源点距离为0 for(int i=1;i<=m;i++){ int a,b,c; cin>>a>>b>>c; e[i].u=e[i+m].v=a;//双向边 e[i].v=e[i+m].u=b; e[i].w=e[i+m].w=c; } ford(1); if(dis[n]==0x3f3f3f3f) cout<<-1; else cout<<dis[n]; return 0; }4. 笔记：SPFA vs Bellman-Ford
很多同学纠结于负权边算法的选择，这里统一总结：
正权图：无脑选Dijkstra。
负权图 (无负环)：首选SPFA。它是 Bellman-Ford 的队列优化版，平均效率高出几十倍。
什么时候用 Bellman-Ford？
题目限制路径最多经过k条边。
图极其稠密或特殊构造，导致 SPFA 退化严重（极罕见）。
