给定一个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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=
510,M=
10010;
int dis[N],backup[N],n,m,k;
struct F{
int a;
int b;
int c;
}f[M];
int bellman_ford(){
memset(dis,0x3f,
sizeof(dis));
dis[1]=
0;
for(
int i=
0;i<k;i++
){
memcpy(backup,dis,sizeof(dis));
for(
int j=
0;j<m;j++
){
int a=f[j].a,b=f[j].b,c=
f[j].c;
if(backup[a]!=
0x3f3f3f3f)dis[b]=min(dis[b],backup[a]+
c);
}
}
if(dis[n]==
0x3f3f3f3f)
return -
1;
return dis[n];
}
int main(
void){
cin>>n>>m>>
k;
for(
int i=
0,a,b,c;i<m;i++
){
scanf("%d%d%d",&a,&b,&
c);
f[i]=
{a,b,c};
}
if(bellman_ford()==-
1)cout<<
"impossible"<<
endl;
else cout<<bellman_ford()<<
endl;
return 0;
}
转载于:https://www.cnblogs.com/programyang/p/11191532.html
