星际航线的最小能耗-最短路板子题

题目描述：

在茫茫宇宙中分布着n个星际空间站（编号为1到 n）。为了建立联络，空间站之间开通了m条单向的虫洞航线。每条航线从空间站u通向空间站v，通行需要消耗w单位的能量。

作为舰队指挥官，你目前位于编号为s的指挥部空间站。现在的任务是：

1. 计算从指挥部出发，到达宇宙中所有其他空间站所需的最低能量值。

2. 此外，必须规划出前往关键战略点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. 一张表看懂区别

2. 深度解析

• Dijkstra 的本质是“贪心”

  • 它利用优先队列维护当前距离最小的点 1。

  • 逻辑：每次从堆中拿出距离最近的点，那个点的最短路就彻底锁死了（vis[u]=1），之后不会再被更新 2。

  • 局限：如果有负权边，后面可能会出现“更短的回路”让前面的贪心判断出错，所以它只能跑非负权图。

• Ford 的本质是“暴力松弛”

  • 它不挑食，每一轮都把图中所有的M条边拿出来试一遍（松弛一遍）。

  • 逻辑：根据图论性质，一个点到起点的最短路径最多经过N-1条边。所以它硬性循环N-1次，确保每个点都被松弛透了。

  • 优势：正因为它甚至会去更新已经算过的点，所以它能兼容负权边。

3. 一句话总结

• 见图就用 Dijkstra（记得开long long和堆优化），除非题目明确说了“边权可能为负”，这时候再考虑Ford或SPFA。