题目描述
给定一个 $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
时间复杂度
$O(nm)$
参考文献
Bellman-Ford算法核心思想:
备份原因:
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510, M = 10010;
int n, m, k;
int dist[N]; // 从起点到该点的最短距离
int backup[N]; // 备份数组
struct Edge{
int a, b, w;
}edges[M];
bool bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
// Bellman-Ford算法核心
for (int i=0; i < k; i++)
{
// 将dist备份, 每次使用上一次的迭代结果
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);
}
}
// 如果 k = 1 并且只有一条边从 结点1 到结点2, 权重为-1, 则dist[n] = -1, 因此不能返回-1作为判断条件
if (dist[n] > 0x3f3f3f3f/2) return false;
else return true;
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
// 初始化
for (int i = 0; i < m; i++)
{
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
edges[i] = {a, b, w};
}
if (!bellman_ford()) puts("impossible");
else printf("%d\n", dist[n]);
return 0;
}