最短路径（二）Bellman_Ford（负权）

AcWing 853. 有边数限制的最短路

给定一个n个点m条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出从1号点到n号点的最多经过k条边的最短距离，如果无法从1号点走到n号点，输出impossible。
注意：图中可能 存在负权回路 。

输入格式
第一行包含三个整数n，m，k。
接下来m行，每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。

输出格式
输出一个整数，表示从1号点到n号点的最多经过k条边的最短距离。
如果不存在满足条件的路径，则输出“impossible”。

数据范围
1≤n,k≤500,
1≤m≤10000,
任意边长的绝对值不超过10000。

输入样例：
3 3 1
1 2 1
2 3 1
1 3 3
输出样例：
3

Bellman_Ford算法思路：
第一步：初始化所有的点，每个点保存原点距该点的距离
第二步：循环遍历所有的边，进行松弛计算dist[u.b] = min(dist[u.b], last[u.a] + u.c);
第三步：遍历途中所有的边edge(u, v),判断是否d(v) > d(u) + w(u,v),若是则返回false,表示途中存在从源点可达的权为负的回路。
本题迭代k次，求出从源点即一号点经过不超过k条边，走到每个点的最短距离。

注意：输出-1的判断条件不是dist[n] == 0x3f3f3f3f.而是dist[n] > 0x3f3f3f3f / 2.
这是因为Bellman_Ford算法里的数据可能存在负权边。在一个存在负权的环里，dist的值会不断的减小，但是由于m, k是有限的，dist也不会减太多，最多减500万次,因此dist[n]的值可能就不是设定的0x3f3f3f3f.

Code:

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 510, M = 10010;
int n, m, k;
int dist[N], last[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(last, dist, sizeof dist);for(int j = 0; j < m; j ++){
    auto u = edges[j];dist[u.b] = min(dist[u.b], last[u.a] + u.w);}}if(dist[n] > 0x3f3f3f3f / 2)  return -1;return dist[n];
}int main()
{
    cin >> n >> m >> k;for(int i = 0; i < m; i ++){
    int a, b, c;cin >> a >> b >> w;edges[i] = {
    a, b, w}; }int t = bellman_ford();if(t == -1)  cout << "impossible" << endl;else  cout << t << endl;return 0;
}