【最短路——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;
}