# 背景

给定一个 $n$ 个点 $m$ 条边的有向图，图中可能存在重边和自环，边权可能为负数
请你求出 $1$ 号点到 $n$ 号点的，最多经过 $k$ 条边的最短距离，如果无法从 $1$ 号点走到 $n$ 号点，输出 impossible

# 数据范围

$1 \le n, k \le 500$
$1 \le m \le 10000$
$1 \le x, y \le n$

# 思路

用结构体记录路径，经历 $k$ 次循环，每次循环都对 d[i] 进行更新，最后判断 d[n] 是否大于一个很大的数（ $0x3f3f3f3f / 2$ ）
注意：有负权边环的图，是有可能没有最短路的

C++

struct Point {
    int a, b, w;
} p[N];

int n, m, k, d[N], bu[N];

int bellman() {
    memset(d, 0x3f, sizeof d), d[1] = 0;
    for (int i = 1; i <= k; i++) {
        memcpy(bu, d, sizeof d);
        for (int j = 1; j <= m; j++) {
            Point t = p[j];
            d[t.b] = min(d[t.b], bu[t.a] + t.w);
        }
    }

    return (d[n] > 0x3f3f3f3f / 2 ? -1 : d[n]);
}

void solve () {
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++)
        cin >> p[i].a >> p[i].b >> p[i].w;
    
    if (bellman() == -1 && d[n] != -1)
        cout << "impossible\n";
    else
        cout << d[n] << "\n";
}

需要注意的是：

每次遍历使用 $min$ 时，应该比较当前的 d[i] 和上一次循环备份的 backup[t.a] + t.w
因此，每次遍历更新之前，应该 memcpy 拷贝一遍 $d$ 数组
为什么是 d[n] > 0x3f3f3f3f / 2 而不是 d[n] == 0x3f3f3f3f
如果存在一条 $point_j \to point_n$ ， $point_j$ 不能被走到，且这条边边权为负数
则 $point\_n$ 的 $d$ 会被更新，不再是 $0x3f3f3f3f$

图论最短路