acwing 853. 有边数限制的最短路

本文主要是介绍acwing 853. 有边数限制的最短路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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

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

输入格式
第一行包含三个整数 n,m,k。

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

点的编号为 1∼n。

输出格式
输出一个整数，表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。

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

数据范围
1≤n,k≤500,
1≤m≤10000,
1≤x,y≤n，
任意边长的绝对值不超过 10000。

输入样例：
3 3 1
1 2 1
2 3 1
1 3 3
输出样例：
3

需要back数组原因：

backup[j]表示每次进入第2重循环的dist数组的备份

为了避免如下的串联情况，在边数限制为一条的情况下，节点3的距离应该是3，但是由于串联情况，利用本轮更新的节点2更新了节点3的距离，所以现在节点3的距离是2。
在这里插入图片描述
正确做法是用上轮节点2更新的距离–无穷大，来更新节点3，再取最小值，所以节点3离起点的距离是3。

实现代码

for (int i = 0; i < k; i ++ )
{memcpy(backup, dist, sizeof dist);for (int j = 0; j < m ; j ++ ){int a = edges[j].a, b = edges[j].b, w = edges[j].w;dist[b] = min(dist[b], backup[a] + w);}
}

为什么是dist[n]>0x3f3f3f3f/2，而不是dist[n]>0x3f3f3f3f
5号节点距离起点的距离是无穷大，利用5号节点更新n号节点距离起点的距离，将得到10⁹−2, 虽然小于10⁹, 但并不存在最短路，(在边数限制在k条的条件下)

在这里插入图片描述

bellman-Ford 算法：

#include<iostream>
#include<cstring>using namespace std;const int N = 510, M = 10010;struct Edge {int a;int b;int w;
} e[M];//把每个边保存下来即可
int dist[N];
int back[N];//备份数组防止串联
int n, m, k;//k代表最短路径最多包涵k条边int bellman_ford() {memset(dist, 0x3f, sizeof dist);dist[1] = 0;for (int i = 0; i < k; i++) {//k次循环memcpy(back, dist, sizeof dist);for (int j = 0; j < m; j++) {//遍历所有边int a = e[j].a, b = e[j].b, w = e[j].w;dist[b] = min(dist[b], back[a] + w);//使用backup:避免给a更新后立马更新b, 这样b一次性最短路径就多了两条边出来}}return dist[n];
}int main() {scanf("%d%d%d", &n, &m, &k);for (int i = 0; i < m; i++) {int a, b, w;scanf("%d%d%d", &a, &b, &w);e[i] = {a, b, w};}int res = bellman_ford();// if (res == -1) puts("impossible");// else cout << res;if (res > 0x3f3f3f3f / 2) puts("impossible");else cout << res << endl;return 0;
}