跳转链接
https://www.acwing.com/problem/content/855/ 来源：模板题,Airbnb面试题
题目描述
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。 请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。 注意：图中可能 存在负权回路 。
输入格式 第一行包含三个整数 n,m,k。 接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。 输出格式 输出一个整数，表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。 如果不存在满足条件的路径，则输出 impossible。 数据范围 1 , 500 , 1 $≤$10000, 任意边长的绝对值不超过 10000。 输入样例
3 3 1 1 2 1 2 3 1 1 3 3 输出样例 impossible 3
题解思路
参考https://www.acwing.com/solution/content/9188/ TIPS: 1、在下面代码中，是否能到达n号点的判断中需要进行if(dist[n] > INF/2)判断，而并非是if(dist[n] == INF)判断 原因是INF是一个确定的值，并非真正的无穷大，会随着其他数值（负数）而受到影响，dist[n]大于某个与INF相同数量级的数即可 2、bellman - ford算法擅长解决有边数限制的最短路问题
代码
cpp
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510, M = 10010;
int n, m, k, a, b, w;
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;
dist[b] = min(dist[b], backup[a] + w);
}
}
if (dist[n] > 0x3f3f3f3f / 2) return 0; // 因为存在负权值
return dist[n];
}
int main()
{
cin >> n >> m >> k;
for (int i = 0; i < m; i++)
{
cin >> a >> b >> w;
edges[i] = {a, b, w};
}
int t = bellman_ford();
if (t == 0) cout << "impossible";
else cout << t;
return 0;
}
