使用图论技巧——有遍数限制的最短路

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

请你求出从 11 号点到 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

    Bellman - ford 算法是求含负权图的单源最短路径的一种算法，效率较低，代码难度较小。其原理为连续进行松弛，在每次松弛时把每条边都更新一下，若在 n-1 次松弛后还能更新，则说明图中有负环，因此无法得出结果，否则就完成。
(通俗的来讲就是：假设 1 号点到 n 号点是可达的，每一个点同时向指向的方向出发，更新相邻的点的最短距离，通过循环 n-1 次操作，若图中不存在负环，则 1 号点一定会到达 n 号点，若图中存在负环，则在 n-1 次松弛后一定还会更新)

对于含有负权边的问题，不能使用dijkstra进行求解

代码演示：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;const int N = 550,M = 100010;
int n,m,k;
int dist[N],backup[N];// backup数组是复制上一次dist数组中的值 struct Edge
{int a,b,w;
} edge[M];void bellman_ford()
{memset(dist,0x3f,sizeof dist);dist[1] = 0;for(int i=0;i<k;i++){//备份数组的作用是防止串联，//串联这个词可能很抽象很多人不理解，我们考虑这样一个场景，//在一次迭代中 我们分别更新dist[2]dist[3] 2->3,如果我们直接使用dist数组进行更新，//那么dist[3]就会用 更新过的dist[2] 来更新dist[3],这里实际上是 dist[1] + w(1, 2) + w(2, 3)，//这意味着我们使用了两条边来更新dist[3],这是不符合要求的，所以我们需要备份数组来确保每次迭代只会使用一条边来更新 dist数组，//这样每次更新使用的边数就在我们的可控范围之内。//通过使用备份数组，我们每次迭代 都会比上一次多使用一条边，是逐次增加的，最后我们就可以得到最大使用k条边的结果memcpy(backup,dist,sizeof dist);for(int j=0;j<m;j++){int a = edge[j].a,b = edge[j].b,w = edge[j].w;dist[b] = min(dist[b],backup[a]+w);}}}int main(void)
{// n 是图中的点数，m 是总共的边数,k 是限制的路径数 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);edge[i] = {a,b,w};}bellman_ford();// 这里是因为如果存在负权边是，则不会有更新操作 if(dist[n]> 0x3f3f3f3f/2) puts("impossible");else printf("%d\n",dist[n]);return 0;
}