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

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