题目描述：
在茫茫宇宙中分布着n个星际空间站（编号为1到 n）。为了建立联络，空间站之间开通了m条单向的虫洞航线。每条航线从空间站u通向空间站v，通行需要消耗w单位的能量。
作为舰队指挥官，你目前位于编号为s的指挥部空间站。现在的任务是：
计算从指挥部出发，到达宇宙中所有其他空间站所需的最低能量值。
此外，必须规划出前往关键战略点obj空间站的具体航行路线（按顺序输出经过的空间站编号）。
输入格式：
第一行包含四个整数n, m, s, obj，分别代表空间站数量、航线数量、出发点编号以及需要输出路径的目标点编号。
接下来的 m 行，每行包含三个整数u, v, w，表示存在一条从u到v的单向航线，权值为w。
输出格式：
第一行输出n个整数。第i个整数表示从出发点s到第i个空间站的最小能量消耗。如果某个空间站无法到达，请输出2^{31}-1。
第二行输出一个序列，表示从s到obj的最短路径上依次经过的空间站编号（包括起点和终点），以空格分隔。
测试样例
输入：
3 3 1 2 1 2 15 1 3 6 3 2 7输出：
0 13 6 2 3 1完整代码：
/* //case2 单源最短路径模版（Dijkstra+邻接表） #include <iostream> #include <queue> using namespace std; const int maxn=10010; int dis[maxn];//储存每个点到出发点的距离 int vis[maxn];//记录每个点有没有被点亮 int pre[maxn];//记录每个点的前驱 int h[maxn];//邻接表记录头指针数组 int vtex[2*maxn]; int nxt[2*maxn]; int wt[2*maxn];//邻接表记录每个点权重 int n,m,s,obj; int idx; struct node{ int u,v,w; friend bool operator <(node a, node b){ return a.w>b.w; } }; priority_queue<node> q; void dijkstra(int s){ dis[s]=0; node tmp; tmp.u=s; tmp.v=s; tmp.w=0; q.push(tmp); while(!q.empty()){ tmp=q.top();//找到堆中最小的 即离起点距离最近的 q.pop();//堆首出堆 int nid=tmp.v;//记录这点的编号 if(vis[nid]==1) continue;//如果这点已经被点亮了就跳过 vis[nid]=1;//没被点亮就现在点亮它 int p=h[nid];//让p等于这个点的头指针 while(p!=-1){ if(vis[vtex[p]]==0){ if(dis[nid]+wt[p]<dis[vtex[p]]){ dis[vtex[p]]=dis[nid]+wt[p]; pre[vtex[p]]=nid; tmp.u=nid; tmp.v=vtex[p]; tmp.w=dis[vtex[p]]; q.push(tmp); } } 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>>s>>obj; memset(h,-1,sizeof(h));//初始化头指针数组 for(int i=1;i<=maxn;i++) dis[i]=2147483647;//初始化dis数组为无穷 memset(vis,0,sizeof(vis));//初始化vis数组都没有被点亮 for(int i=1;i<=n;i++) pre[i]=i;//初始化每个点前驱都是自己 //邻接表建图 for(int i=1;i<=m;i++){ int u,v,w; cin>>u>>v>>w; addedge(u,v,w); } //dijkstra dijkstra(s);//出发点 for(int i=1;i<=n;i++) cout<<dis[i]<<" ";//输出每个点到s点点最短距离 cout<<endl; //接下来输出路径 int cnt=obj; while(cnt!=s){ cout<<cnt<<" "; cnt=pre[cnt]; } cout<<s;//最后输出起点 return 0; } */ //case2 单源最短路径模版 （Ford算法） #include <iostream> using namespace std; int n,m,s,obj; struct edge{ int u; int v; int w; }; edge e[10010];//存着所有边 int dis[10010];//存每个点到源点的距离 int pre[10010];//记录每个点的前驱 void ford(int s){ dis[s]=0; for(int i=1;i<n;i++){//迭代n-1次 bool flag=false;//记录本轮是否发生松弛 for(int j=1;j<=m;j++){//每个点用所有边去松弛 //当一条边的起点到源点的距离+边权<这条边终点到源点的距离，就更新终点到源点的距离，且起点到源点的距离不能为无穷，不然加边权就超范围了 if(dis[e[j].u]+e[j].w<dis[e[j].v] && dis[e[j].u]!=2147483647){ dis[e[j].v]=dis[e[j].u]+e[j].w; flag=true; pre[e[j].v]=e[j].u; } } if(flag==false) break;//如果这一轮没有任何更新，说明最短路已经确定，不用再跑了 } } int main(){ cin>>n>>m>>s>>obj; //存边 for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w; for(int i=1;i<=n;i++) pre[i]=i;//初始化每个点的前驱为自己 for(int i=1;i<=n;i++) dis[i]=2147483647;//初始化dis数组为无穷 ford(s); for(int i=1;i<=n;i++) cout<<dis[i]<<" "; cout<<endl; //接下来输出路径 int cnt=obj; while(cnt!=s){ cout<<cnt<<" "; cnt=pre[cnt]; } cout<<s;//最后输出起点 return 0; }【核心对比】Dijkstra vs Ford 算法
1. 一张表看懂区别
| 维度 | Dijkstra (堆优化) | Ford (Bellman-Ford) |
| 时间复杂度 | O(Mlog N)(快，接近线性) | O(N*M)(慢，容易TLE) |
| 核心思想 | 贪心策略(Greedy) | 动态规划/暴力松弛(DP) |
| 处理负权边 | ❌ 不支持(一旦有负边，贪心失效) | ✅ 支持(专门处理负权) |
| 判断负权环 | 无法判断 | 可以判断 (第N次还能松弛即有环) |
| 适用场景 | 90%的题目(非负权图的首选) | 边数很少、有负权边、或需判环时 |
2. 深度解析
Dijkstra 的本质是“贪心”
它利用优先队列维护当前距离最小的点 1。
逻辑：每次从堆中拿出距离最近的点，那个点的最短路就彻底锁死了（
vis[u]=1），之后不会再被更新 2。局限：如果有负权边，后面可能会出现“更短的回路”让前面的贪心判断出错，所以它只能跑非负权图。
Ford 的本质是“暴力松弛”
它不挑食，每一轮都把图中所有的M条边拿出来试一遍（松弛一遍）。
逻辑：根据图论性质，一个点到起点的最短路径最多经过N-1条边。所以它硬性循环N-1次，确保每个点都被松弛透了。
优势：正因为它甚至会去更新已经算过的点，所以它能兼容负权边。
3. 一句话总结
见图就用 Dijkstra（记得开
long long和堆优化），除非题目明确说了“边权可能为负”，这时候再考虑Ford或SPFA。
