代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=510,M=10010;
int n,m,k;
int dist[N],backup[N];
struct Edge{
int a,b,w;
}edge[M];
void Bellman_Ford(){
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++){//m条边
int a=edge[j].a,b=edge[j].b,w=edge[j].w;
dist[b]=min(dist[b],backup[a]+w);
}
}
}
int main(){
cin>>n>>m>>k;
for(int i=0;i<m;i++){
int x,y,z;
cin>>x>>y>>z;
edge[i]={x,y,z};//结构体的赋值
}
Bellman_Ford();
if(dist[n]>0x3f3f3f3f/2) cout<<"impossible"<<endl;//注:不能用-1作为返回值来表示走不到n号点,因为有可能最近的点就是-1,结果被impossible了
else cout<<dist[n]<<endl;
return 0;
}