bellman-ford算法

今天，我们来讲讲第二种最短路算法，boolman_ford算法，这个算法可以用来处理两种情况

第一种是含有 边权可能为负数 这种情况
第二种是 给定了步数 的这种情况

接下来给的这道题就是典型的只可以使用boolman_ford算法解决的，如果用spfa算法(另外一种负权类最短路算法)的话会被控时间

题目

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

算法分析

我们在进行讲解算法前，我们需要先知道一下边权为负数是个什么样的情况

为了更好的表达意思，我在下面的文章会统一把a指向b的线所占的负权的值c用{a,b,c}表示

我们可以看看左上角的那幅图，图中的{3,4,-2},{4,2,-4}指的是3到4和4到2所占的负权边，一个是-2，另一个是-4

我还是来讲一个故事吧

小故事

我们现在遇到了一个抽奖大冒险，我们可以选择无数次机会，去走我们想要的路，在道路中我们会的得到钱或者失去钱，假设+3是我们失去了三块钱，老板得到了3块钱的意思，-3是我们得到了三块钱，老板失去了3块钱的意思，我们把上面的图再搬运过来，我们可以从1 - 2，2 - 3，3 - 4，4 - 2，2 - 3，3 - 4，4 - 2，2 -3......无限循环下去，这样的话，老板就会一直亏钱，直到全部赔完，相反，我们会拿钱拿到手软(天哪，世上怎么会有这种好事)

所以老板为了限制我们获得无数的钱，便制定了一条手段，就说我们最多可以走多少步，最后所得到的结果就是我们获得的最后的钱(可能会赔钱)，这也是使用boolman_ford算法的两条定律(如开头)

算法构造

现在，我们就可以通过上面的小故事来了解我们的算法原理了，就是说在限定的次数内，我们要尽可能地走向终点

为了更好地存储我们的点以及两个点之间的权，我们创立一个结构体变量(结构体就不用解释了吧…)

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 510, M = 100010;
struct Edge
{
    int a, b, c;
}edge[M];

紧接着,我们再定义相关变量

int n, m, k;
int last[N], dist[N];

dist[N]是用来存储我们的每个点到原点的最近距离的，而last[N]是用来记忆我们的上上步是怎么走的

last的理解

​ 还记得之前的第一篇最短路的博客吗？里面的小故事有提到过桥的概念，就是说我们每走一步，都会更新我们的位置，但是在这个题中我们不可以用那种思维来写，请看此题

要求: 我们要在1步之内走到终点

图
  1    1
1 -> 2 -> 3
 \-------/
     3

上面那幅图，如果我们按照走桥的思维走，我们最少只要2的权，但是需要走2步，这是不合理的

     1    2   3    (00指无穷)
第0步 0   00  00
第1步 0    1  00
第2步 0    1   2

我们要满足题目所给的要求，这就需要我们走下面那个权为3的桥，这才可以满足题目中走一步的要求

     1    2   3    (00指无穷)
第0步 0   00  00
第1步 0    1  00
第2步 0    1   3    (用last记录了上上步的位置)

定义类代码书写

定义代码如下

int main()
{
	//按照题目要求输入
    scanf("%d%d%d", &n, &m, &k);
    int i;
    //一共有m次相连接的点
    for (i = 0; i < m; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        edge[i] = { a,b,c };
    }
    //进入函数
    int t = boolmen_ford();
    //判断并输出
    if (t > 0x3f3f3f3f / 2) puts("impossible");
    else printf("%d", t);
    return 0;
}

算法实现

int boolmen_ford()
{
	//初始化所有的距离离原点为无穷
    memset(dist, 0x3f, sizeof(dist));
    //初始化第一个点即原点到原点的距离为0
    dist[1] = 0;
    int i;
    //一共最多k步
    for (i = 0; i < k; i++)
    {
    	//记忆化
        memcpy(last, dist, sizeof(dist));
        //对于每个找到的新点更新
        for (int j = 0; j < m; j++)
        {
        	//自动变量识别
            auto e = edge[j];
            //求在k步之内的最小权
            dist[e.b] = min(dist[e.b], last[e.a] + e.c);
        }
    }
    //返回值
    return dist[n];
}

结尾的话

首先,希望个位如果看到有什么错误的地方，或者说对于某些语句有更好的解释的话，烦请告知我(qq1594463152),我看到后会立刻修改自己的错误和错误的思考方向

另外,如果你用心看到这里的话，相信你一定可以学有所获！不过多多练习才是最重要的哦

引入

———引自acwing算法基础课

​ yxc主讲