题目描述

特殊条件：

由于有边树限制，需要备份，保证使用的是上一次迭代的结果。
否则可能使用了后面的节点使用了当前节点更改后的结果，这样就没有边树限制了。
创建一个备份数组backup[]
并且因为存在边数限制，不会造成没有最小路的情况。

步骤

存在从a到b的边，权重w
1.循环所有点：
2.循环所有边
迭代次数k：从1号点经过不超过k条边，走向最短路的距离
3. 松弛操作：
Dist[b] = min(dist[b], dist[a] + w) 
循环之后，所有边都满足
三角不等式：Dist[b] <= dist[a] + w

$\cal{question1:}$不需要状态数组？
$\cal{Answer:}$再dijkstra算法中，状态数组是结合st，表示距离点1最近的集合，每次都需要找除了这个集合之外最小距离的点;
在bellman算法里，每次更新一条边上的两个点（边信息可以用邻接表或者结构体存放），第一层循环限定了最多找重复多少次，就不需要再加限定了。

$\cal{question2:}$为什么之前的朴素算法dijkstra 循环点，而这次循环边？
$\cal{Answer:}$本质上都是一样的，最后都是更新点。

$\cal{question3:}$为什么dijkstra算法不能求负边？
$\cal{Answer:}$由于有st[]的存在，加负边也可以。

$\cal{question4:}$为什么要循环点再循环边？
$\cal{Answer:}$第一层循环并不是循环点，而是有边数限制，第一层循环次数是边的次数。
如果循环了n次，还是会更新dist， 那么就存在负环。

样例

3 3 1
1 2 1
2 3 1
1 3 3

算法1

(bellman ford) $O(nm)$

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;
const int N = 510, M = 10010;
struct Edge{
int a, b, w;    
}edges[M];

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

int bellford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] =0;
    for(int i = 1; i <= k; ++i)
    {
        memcpy(backup, dist, sizeof dist);
        for(int j = 1; j <= m; ++j)
        {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            dist[b] = min(dist[b], backup[a] + w);
        }
    }
    /*可能存在负边*/
    if(dist[n] > 0x3f3f3f3f / 2)return -1;
    return dist[n];
}

int main()
{
    int a, b, c;
    cin >> n >>m >> k;
    for(int i = 0; i < m; ++i)
    {
        cin >> a >> b >> c;
        edges[i].a = a; edges[i].b = b; edges[i].w = c;
    }
    int z = bellford();
    if(z == -1)puts("impossible");
    else cout << z << endl;
    return 0;
}