题目描述
给定一个n个点m条边的有向图,图中可能存在重边和自环, 边权可能为负数。
请你求出从1号点到n号点的最多经过k条边的最短距离,如果无法从1号点走到n号点,输出impossible。
注意:图中可能 存在负权回路 。
算法:bellman_ford算法
时间复杂度:O($N·M$)
需要注意
(1)判断距离不存在是的时候需要判断的门限是INF/2,不在是INF。主要原因是存图的方式:邻接表的方式一般不会发生更新不存在的路径,而其他的存图方式可能会更新不存在的路径(结构体 邻接矩阵)
(2)bellman_ford算法不仅可以求出在边数限(不超过)的条件下的最短路,还可以求出在边数恰好为k的最短路径
(3)循环次数代表从k-1边的最短路径向k条边的最短路进行转移(从集合的角度分析问题)
C++代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=510,M=10010;
int n,m,k;
int dist[N];
int last[N]; //防止发生串联
struct Range
{
int a,b,w;
}range[M];
int bellman_ford()
{
memset(dist,0x3f,sizeof dist);
dist[1]=0;
//路径最大的限制条数是k
for(int i=0;i<k;i++){
memcpy(last,dist,sizeof last);
for(int j=0;j<m;j++){
auto e=range[j];
dist[e.b]=min(dist[e.b],last[e.a]+e.w);
}
}
if(dist[n]>0x3f3f3f3f/2)return -1;
return dist[n];
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<m;i++){
int a,b,w;
scanf("%d%d%d",&a,&b,&w);
range[i]={a,b,w};
}
int t=bellman_ford();
if(t==-1)cout<<"impossible"<<endl;
else cout<<t<<endl;
return 0;
}