题目描述
给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环, 边权可能为负数。
请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离,如果无法从 1 号点走到 n 号点,输出 impossible。
注意:图中可能 存在负权回路 。
输入格式
第一行包含三个整数 n,m,k。
接下来 m 行,每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。
输出格式
输出一个整数,表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。
如果不存在满足条件的路径,则输出 impossible。
数据范围
1≤n,k≤500,
1≤m≤10000,
任意边长的绝对值不超过 10000
样例
输入样例:
3 3 1
1 2 1
2 3 1
1 3 3
输出样例:
3
bellman_ford算法详解
串联问题
要求k=1,求3号点距1号点的距离
用1号点更新2号点,此时2号点距离为1,在bellman_ford算法中会依次遍历所有边
所以3号点的距离会由2号点更新为2,但是此时由1号点到3号点的边数是2,大于了k的范围
所一这个答案是不正确的,我们从图可以看出答案应为3,所以此时发生了串联
这是我们用banckup备份上次的距离来更新这个点就不会发生这个问题
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int p=10010;
int n,m,k;
int d[p],backup[p];//d表示点离起点的距离,backup表示备份上次循环取得的最短距离
struct Edge
{
int a,b,w;//w表示从a到b的边的权重
}edges[p];
int bellman_ford()
{
memset(d,0x3f,sizeof d);//初始化为无穷大
d[1]=0;//起点为0
for(int i=0;i<k;i++)//因为题目要求k条边,每次循环都往外延伸一条边
{
memcpy(backup,d,sizeof d);//备份上次循环保留的距离,防止串联
//串联是指给定了k条边,但是更新某一个点i的距离时会通过这个更新的点来更新跟他相连的下一个点j
//但由于k的限制,这个点j由i更新的距离可能会超过k,但是会有小于k条边的距离存在
//所有导致j的距离出错,即串联,可以看y总举的例子
for(int j=0;j<m;j++)//依次遍历m条边
{
int a=edges[j].a,b=edges[j].b,w=edges[j].w;//取出每条边的a,b和权重
d[b]=min(d[b],backup[a]+w);//能更新距离的话就更新距离但要用上次循环的距离来更新点b的距离
//避免a更新后立马更新b导致超过k的范围,之后点b的距离可能不会再更新导致串联,这样求得的距离
//时不对的
}
}
if(d[n]>0x3f3f3f3f/2) return -1;//为何除以2?若两个点都是无穷大,但是是负权重
//则更新某个点时这个点距离起点的距离可能会小于0x3f3f3ff,所以除以二来保证这个点不满足条件
else return d[n];
}
int main()
{
cin>>n>>m>>k;
for(int i=0;i<m;i++)
{
int a,b,w;
cin>>a>>b>>w;
edges[i]={a,b,w};
}
int t=bellman_ford();
if(t==-1) cout<<"impossible";
else
cout<<t;
return 0;
}