题目链接:https://www.acwing.com/problem/content/description/855/
贝尔曼福特负权模板,额外占用的空间就是 n的数量,用覆盖的方式实现。
实现起来挺容易的,在贝尔曼福特上面改改就可以了
#include<bits/stdc++.h> using namespace std; const int N=100010; int dist[N],backup[N]; int k,n,m; struct edge{ int a;int b;int w; }edge[N]; int bellman_ford() { memset(dist,0x3f,sizeof dist); dist[1]=0; for(int i=1;i<=k;i++) { memcpy(backup,dist,sizeof dist); for(int j=1;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() { cin>>n>>m>>k; for(int i=1;i<=m;i++) { int a,b,c; cin>>a>>b>>c; edge[i].a=a,edge[i].b=b,edge[i].w=c; } int t=bellman_ford(); if(t>=0x3f3f3f3f/2)puts("impossible"); else cout<<t<<endl; }