853. 有边数限制的最短路
题目传送门
题目链接
题目描述
给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。求出从1号点到n号点的最多经过k条边的最短距离，如果无法到达则输出"impossible"。
题目分析
这道题要求我们在有边数限制的情况下找到最短路径，且图中可能存在负权边甚至负权回路。这种情况下，Dijkstra算法无法适用，而Bellman-Ford算法可以解决这类问题。
解题思路
- 初始化距离数组：将起点距离设为0，其他点设为无穷大
- 松弛操作：进行k次松弛操作，每次遍历所有边，尝试更新最短距离
- 防止串联更新：使用备份数组确保每次迭代只使用上一步的结果
- 结果判断：检查最终距离是否可达
算法讲解（Bellman-Ford）
Bellman-Ford算法通过松弛操作逐步逼近最短路径。对于有边数限制的最短路问题：
- 每次迭代表示最多经过i条边的最短距离
- 使用备份数组防止在一次迭代中多次更新
- 经过k次迭代后，得到最多经过k条边的最短距离
例子：
输入：
3 3 1
1 2 1
2 3 1
1 3 3
过程：
- 初始dist[1]=0,其他INF
- 第一次迭代：
- 更新dist[2]=1
- 更新dist[3]=3（直接从1到3）
- 结果：dist[3]=3
代码实现
#include <bits/stdc++.h>
using namespace std;const int N = 510, M = 10010;
const int INF = 0x3f3f3f3f;struct Edge {int a, b, w;
} edges[M];int n, m, k;
int dist[N];
int backup[N];int bellman_ford() {memset(dist, INF, 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] > INF / 2) return INF;return dist[n];
}int main() {cin >> n >> m >> k;for (int i = 0; i < m; i++) {int a, b, w;cin >> a >> b >> w;edges[i] = {a, b, w};}int res = bellman_ford();if (res == INF) puts("impossible");else cout << res << endl;return 0;
}
重点细节
- 备份数组：必须使用备份数组保存上一步结果，防止串联更新
- 无穷大判断：由于负权边可能减少距离，使用INF/2判断是否可达
- 结构体存边：Bellman-Ford通常直接遍历所有边，用结构体存储更方便
复杂度分析
- 时间复杂度：O(k*m)，其中k是迭代次数，m是边数
- 空间复杂度：O(n+m)，存储距离和边集
总结
Bellman-Ford算法是解决有边数限制最短路问题的经典算法，尤其适用于含负权边的图。关键点在于理解松弛操作和备份数组的作用，以及如何处理无穷大的情况。