【最短路——Bellman_Ford算法】AcWing 853. 有边数限制的最短路

AcWing 853. 有边数限制的最短路[Bellman_Ford算法]

这里有两个点需要说明一下：

1. 在下面代码中，是否能到达n号点的判断中需要进行

   if(dist[n] > INF/2)

   判断，而并非是

   if(dist[n] == INF)

   判断，原因是INF是一个确定的值，并非真正的无穷大，会随着其他数值而受到影响，dist[n]大于某个与INF相同数量级的数即可。
2. 本题比较特殊，下面代码中使用了backup[] 数组是上一次迭代后 dist[] 数组的备份，由于是每个点同时向外出发，因此需要对 dist[] 数组进行备份，若不进行备份会因此发生串联效应，影响到下一个点。但这一点没有理解特别清楚，接下来需要找时间参考一下其他资料理解一下。

代码：

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, M = 10010;

int n, m, k;
int dist[N], backup[N];//dist为每个点到起点的距离，backup是对dsit的一个备份

struct Edge {
    int a, b, w;
}edges[M];

int bellman_ford() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    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);
        }
    }
    
    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    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);
        edges[i] = {a, b, w};
    }
    
    int t = bellman_ford();
    
    if (-1 == t) puts("impossible");
    else printf("%d\n", t);
    
    return 0;
}