给定一个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
AC代码：

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
const   int N=1010;
const   int M=100010;
int h[N],ne[M],e[M],idx,d[N];
int past[N];
int w[M];
bool st[N];
int n,m,k;
void add(int a,int b,int c)
{
   
    w[idx]=c;
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
struct   node
{
   
    int a;
    int b;
    int c;
}edge[M];
int bell_man()
{
   
    memset(d,0x3f,sizeof(d));
    d[1]=0;
    for(int i=1;i<=k;i++)
    {
   
        memcpy(past,d,sizeof(d));//past用来记录上一次d数组
        for(int j=1;j<=m;j++)//枚举m条边
        {
   
            if(d[edge[j].b]>past[edge[j].a]+edge[j].c)
            d[edge[j].b]=past[edge[j].a]+edge[j].c;
        }
    }
    if(d[n]>0x3f3f3f3f/2)   return -1;
    else    return d[n];
}
int main()
{
   
    memset(h,-1,sizeof(h));
    cin>>n>>m>>k;
     for(int i=1;i<=m;i++)
    {
   
        int a,b,c;
        cin>>a>>b>>c;
        edge[i]={
   a,b,c};
    }
    int t=bell_man();
    if(t==-1)
    printf("impossible\n");
    else
    printf("%d\n",t);
    return 0;
}=