bellman

模板题

此算法对所有边进行松弛操作，外循环进行N -1次

解决那些规定最多只能经过K条边到达目标的问题

比如，从  A地飞到B地  的最短路并且A到B转飞机的次数不能超过K

bellman_frod还可以解决负环问题，如果更新了n-1次路径还是很大，说明有负环，有负环就会导致没有最短路

#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N=1e4+10,M=505; int n,m,k; struct node { int a,b,w; }edge[N]; int dis[M],backup[M]; int bellman_ford() { memset(dis,0x3f,sizeof(dis)); dis[1]=0; for(int i=0;i<k;i++) { memcpy(backup,dis,sizeof(dis));//注意这个backup的复制数组很重要，这里是一轮一轮更新，防止内循环的小轮更新干扰 for(int j=0;j<m;j++) { int a=edge[j].a,b=edge[j].b,w=edge[j].w; dis[b]=min(dis[b],backup[a]+w); } } if(dis[n]>0x3f3f3f3f/2)return -1; else return dis[n]; } int main() { cin>>n>>m>>k; for(int i=0;i<m;i++) { int a,b,c; cin>>a>>b>>c; edge[i]={a,b,c}; } int t=bellman_ford(); if(t==-1) cout<<"impossible"<<endl; else cout<<t<<endl; }