题目传送门
首先我们来认识一下Bellman Ford算法,Bellman - ford 算法是求含负权图的单源最短路径的一种算法,效率较低,代码难度较小。其原理为连续进行松弛,在每次松弛时把每条边都更新一下,若在 n-1 次松弛后还能更新,则说明图中有负环,因此无法得出结果,否则就完成。
实现过程
其中 \(back\) 数组表示的是 \(dis\) 数组的备份,防止出现串联问题,就是用这一次更新的节点更新后面的结点。
那接下来就是解决这道例题了
我们这里只要迭代 \(k\) 次即可
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 510, M = 1e4 + 100; int n,m,k; int dist[N], backup[N];//backup防止串联 struct node{ int a,b,w; }edge[M]; int bellman() { 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 = edge[j].a, b = edge[j].b, w = edge[j].w; dist[b] = min(dist[b], backup[a] + w); } } 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); edge[i] = {a,b,w}; } int t = bellman(); if(dist[n] > 0x3f3f3f3f / 2) puts("impossible"); else printf("%d\n", t); return 0; }
时间复杂度\(O(nm)\)