acwing853有边数限制的最短路，bellman算法

初始负无穷；dist[起点]=0；

for （i：1~n）    //若1~k则表示最多走k条边的最短路径
    for 遍历所以边(a->b,距离c)
       b的最短路=min（原b的最短路，原a的最短路+a->b的距离）

#include <bits/stdc++.h>

using namespace std;

int n,k,m,a,b,c;
const int N=505,M=100005;
struct Edge{
	int a,b,c;
};
Edge e[M];
int dist[N],backup[M];

int bell(){
	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=e[j].a, b=e[j].b, c=e[j].c;
			dist[b]=min(dist[b],backup[a]+c);
		}
	}
}

int main() {
	cin>>n>>m>>k;
	for(int i=0;i<m;i++){
		scanf("%d%d%d",&a,&b,&c);
		e[i]={a,b,c};
	}
	bell();
	if(dist[n]<0x3f3f3f3f/2) cout<<dist[n]<<endl;//不用dist[n]==0x3f3f3f3f，因为有可能a=0x3f；a->n,n=0x3f-4 
	else puts("impossible");
	return 0;
}