题目描述

blablabla

样例

blablabla

blablabla

参考文献

https://www.acwing.com/solution/content/14088/

C++ 代码

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

using namespace std;

const int N = 510, M = 1e4 + 10;

struct node
{
    int a, b, val;
}e[M];

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

int bellman_ford()
{
    memset(dist, 0x3f, sizeof(dist));

    dist[1] = 0;

    for(int i = 0; i < k; i++)
    {
        memcpy(back, dist, sizeof dist);
        // 用上一轮更新的节点来更新这一轮的节点， 避免串联的情况
        // eg: 1 ->(1) 2 -> 3(1)  1 -> 3(3)
        // 如果没有back， 1 -> 3 会更新为 2
        // 有了back 1 -> 3 会更新为 3， 其中 1 -> 2 会更新为+无穷

        for(int j = 0; j < m; j++)
        {
            int a = e[j].a, b = e[j].b, val = e[j].val;
            dist[b] = min(dist[b], back[a] + val); // 松弛
        }
    }

    if(dist[n] > 0x3f3f3f3f / 2) return -1; // 因为有负权边的存在
    else return dist[n];
}

int main()
{
    cin>>n>>m>>k;

    for (int i = 0; i < m; i ++)
    {
        int a, b, w;
        cin>>a>>b>>w;
        e[i] = {a, b, w};
    }

    int res = bellman_ford();

    if(res == -1) puts("impossible");
    else cout<<res<<endl;

    return 0;
}