题目描述

blablabla

样例

blablabla

算法1

使用backup数组的目的是为了防止松弛的次数大于k
4 4 1
1 2 1
2 3 1
3 4 2
1 3 -2
在上面这个例子中，如果不用backup数组，
for (int j = 0; j < m; j ++ ) { int a = edges[j].a, b = edges[j].b, w = edges[j].w; if (dist[a] != 0x3f3f3f3f && dist[b] > dist[a] + w){ dist[b] = dist[a] + w; } }
手工模拟一下，里面的松弛次数将会大于k。

C++ 代码

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

using namespace std;

const int N = 510, M = 10010;

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

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;
            if (backup[a] != 0x3f3f3f3f && dist[b] > backup[a] + w){
                dist[b] = backup[a] + w;
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) 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 (t == -1) puts("impossible");
    else printf("%d\n", t);

    return 0;
}