题目描述

给定一个 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

Bellford算法

算法思路:
两重循环遍历,第一重遍历所有点,第二重遍历所有边,每一次将1号点到i点的距离更新为 当前到i点距离与(1号点到k点距离+k到i距离)的最小值

在更新点的时候为了防止串联更新(在某一次更新距离过程中用更新后的距离去更新距离),需要备份dist数组

C++ 代码

#include <cstring>
#include <iostream>
using namespace std;

const int N = 510, M = 10010;

struct Edge {
    int a, b, w;
} edges[M];//存边,a到b有一条长为w的边

int n, m, k;
int dist[N];//到一号点的距离
int last[N];//备份

int bellford() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 0; i < k; ++i) {//由于题目有k条边的限制 所以只更新k次
    //经过不超过k条边的最短路的距离
        memcpy(last, dist, sizeof dist);
        for (int j = 0; j < m; ++j) {//这里取点顺序是不固定的
            Edge e = edges[j];//取边
            dist[e.b] = min(dist[e.b], last[e.a] + e.w);//1号点到b点的距离更新为 当前到b点距离与(1号点到a点距离+a到b距离)的最小值
            //使用last:避免给a更新后又用a更新b
        }
    }

    if (dist[n] > 0x3f3f3f3f / 2)//如果图中存在负权边则有可能某个点距离意义上是无穷大,但是被负权边更新,值比0x3f3f3f3f小
    //所以要判定一下
        puts("impossible");
    else
        printf("%d\n", dist[n]);
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    int a, b, c;

    for (int i = 0; i < m; ++i) {
        scanf("%d%d%d", &a, &b, &c);
        edges[i] = {a, b, c};//赋值
    }
    bellford();
    return 0;
}