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

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

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

#include <bits/stdc++.h>
using namespace std;

const int N = 505, M = 10005;

int n, m, k;    //点数 边数 松弛时最大迭代次数

int dis[N], backup[N];

struct
{

    int a, b, w;
}edges[M];

int bellman_ford()
{

    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;
    for (int i = 0; i < k; ++i) {

        //最多经过k条边到达终点
        memcpy(backup, dis, sizeof dis);    //拷贝上一次迭代的数据，防止在这一次迭代时前面的点影响到后面的点
        for (int j = 0; j < m; ++j) {

            //遍历每一条边
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            dis[b] = min(dis[b], backup[a] + w);
        }
    }
    if (dis[n] < 0x3f3f3f3f / 2) {

        //因为更新的过程中，即使没有迭代到n节点，也可能会有负权边对dis[n]有影响
        return dis[n];
    }
    else
    {

        return -1;
    }

}

int main() 
{

#ifndef ONLINE_JUDGE
    freopen("D:/VS CODE/C++/in.txt", "r", stdin);
    freopen("D:/VS CODE/C++/out.txt", "w", stdout);
#endif
    cin >> n >> m >> k;

    for (int i = 0; i <= m; ++ i ) {

        int a, b, w;
        scanf("%d %d %d", &a, &b, &w);
        edges[i].a = a; edges[i].b = b; edges[i].w = w;
    }

    int t = bellman_ford();

    if (t != -1)
        printf("%d", t);
    else
        cout << "impossible";

    fclose(stdin);
    fclose(stdout);
    return 0;
}