本文共 1297 字，大约阅读时间需要 4 分钟。

给定一个n个点m条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出从1号点到n号点的最多经过k条边的最短距离，如果无法从1号点走到n号点，输出impossible。

注意：图中可能 存在负权回路 。

输入格式

接下来m行，每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。

输出格式

如果不存在满足条件的路径，则输出“impossible”。

数据范围

输入样例：

#include
   
    #include
    
     #include
     
      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;}=