AcWing 853. 有边数限制的最短路
原题链接
简单
作者:
术
,
2021-01-23 15:08:46
,
所有人可见
,
阅读 273
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=505;
const int M=10005;
int dist[N];
int backup[N];
int n,m,k;
struct Edge{
int a;
int b;
int w;
}edges[M];
int bellman(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
for(int i=0;i<k;i++){
memcpy(backup,dist,sizeof dist);
for(int j=0;j<m;j++){
int a=edges[j].a,b=edges[j].b,w=edges[j].w;
dist[b]=min(backup[a]+w,dist[b]);
}
}
if(dist[n]>0x3f3f3f3f/2) return -1;
return dist[n];
}
int main()
{
cin>>n>>m>>k;
for(int i=0;i<m;i++){
int a,b,c;
cin>>a>>b>>c;
edges[i].a=a;
edges[i].b=b;
edges[i].w=c;
}
if(bellman()==-1)
cout<<"impossible";
else
cout<<bellman();
//cout << "Hello world!" << endl;
return 0;
}