acwing853有边数限制的最短路，bellman算法
解决负权边有边数限制的最短路
bellman算法伪代码：
初始负无穷；dist[起点]=0； for （i：1~n） //若1~k则表示最多走k条边的最短路径 for 遍历所以边(a->b,距离c) b的最短路=min（原b的最短路，原a的最短路+a->b的距离）for完n次后dist满足dist【b】<=dist【a】+b；
判断是否有负圈（圈内值和为负数，那么在圈里多转几圈就有负无穷）：
for（i：1~n）中在循环一遍如果dist【1~n】有一个变化就有负圈；如果dist【n】变化则无1->n的最短路
代码：
#include <bits/stdc++.h>
using namespace std;
int n,k,m,a,b,c;
const int N=505,M=100005;
struct Edge{
int a,b,c;
};
Edge e[M];
int dist[N],backup[M];
int bell(){
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=e[j].a, b=e[j].b, c=e[j].c;
dist[b]=min(dist[b],backup[a]+c);
}
}
}
int main() {
cin>>n>>m>>k;
for(int i=0;i<m;i++){
scanf("%d%d%d",&a,&b,&c);
e[i]={a,b,c};
}
bell();
if(dist[n]<0x3f3f3f3f/2) cout<<dist[n]<<endl;//不用dist[n]==0x3f3f3f3f，因为有可能a=0x3f；a->n,n=0x3f-4
else puts("impossible");
return 0;
} 
投递百度等公司10个岗位 >
