柳州网站优化公司_平面设计公司起名_磁力岛引擎_牛推网

 思路

• 外层遍历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;
}