有边数限制的最短路
给定一个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
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
/*
Bellman-ford算法 与 其他单源最短路径算法不同之处是
该算法的题目中要求 “有边数限制”
为实现该要求,使用 k 次循环,每次循环在图中扩展一层;
注意事项:
1. 为保证每次循环都拓展一层,需要对每一条边记录其原始信息;
避免基于前面的边的修改再次更新;
若如此,则循环中就对每一条边更新了超过一次,
未必符合“循环一次拓展一层”的要求;
—— 关键变量:back;
*/
const int N = 510, M = 10010;
// 边的结构体
struct Edge {
int a;
int b;
int w;
} e[M];
int dist[N];
// 记录边权重的原始信息
int back[N];
//k代表最短路径最多包涵k条边
int n, m, k;
int bellman_ford() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
// k次循环,每次循环扩展一层
for (int i = 0; i < k; i++) {
// 记录原始 距离信息;
memcpy(back, dist, sizeof dist);
// 遍历所有边,正无穷者更新无效果,每次拓展一层;
for (int j = 0; j < m; j++) {
int a = e[j].a, b = e[j].b, w = e[j].w;
dist[b] = min(dist[b], back[a] + w);
}
}
// 避免负权值的边对正无穷的边造成影响,
// 由于 边权的绝对值不大于100000
// 负权值边对正无穷的影响必小于 1/2;
if (dist[n] > 0x3f3f3f3f / 2)
return -1;
else
return dist[n];
}
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);
e[i] = { a, b, w };
}
int ans = bellman_ford();
if (ans == -1)
puts("impossible");
else cout << ans << endl;
return 0;
}