Bellman-Ford

 思路

• 外层遍历V-1次
• 内层遍历所有边（共E次），尝试更新起点的终点的dist值
  • 原材料是backup（前次遍历的结果）
  • 维持住性质（见下）

优点

允许负环

允许负权边

有特殊性质

缺点

复杂度达到

例题

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 510, M = 1e4+10;
const int inf = 0x3f3f3f3f;
struct edge{
    int a;
    int b;
    int c;
} e[M];
int n, m, k;
int dist[N], backup[N];
int Bellman()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    for(int i = 0; i < k; i++) //要保持k次遍历有“路径的边数不超过k”的性质，需要backup
    {
        memcpy(backup, dist, sizeof dist);
        for(int j = 0; j < m; j++)
        {
            int a = e[j].a, b = e[j].b, c = e[j].c;
            if(dist[b] > backup[a] + c)
                dist[b] = backup[a] + c; //backup是原材料(<=k-1)，dist是最优的结果(<=k)，当前的最优结果是下次的材料
        }
    }
    
    if(dist[n] > inf / 2) return inf;
    else return dist[n];
}
int main()
{
    cin >> n >> m >> k;
    for(int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        e[i] = {a, b, c};
    }
    int t = Bellman();
    if(t == inf) cout << "impossible";
    else cout << t;
}