社区讨论
关于Bellman_Ford(好像和这个没啥关系)的疑问
灌水区参与者 2已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @m2vz2q67
- 此快照首次捕获于
- 2024/10/30 22:29 去年
- 此快照最后确认于
- 2025/11/04 15:40 4 个月前
CPP
#include<iostream>
#include<cstring>
using namespace std;
const int N=510,M=10010;
struct Edge{
int a;
int b;
int w;
}e[M];//把每个边保存下来即可
int dist[N];
int back[N];//备份数组放置串联
int n,m,k;//k代表最短路径最多包涵k条边
int bellman_ford(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
for(int i=0;i<k;i++){//k次循环
memcpy(back,dist,sizeof dist);
for(int j=0;j<m;j++){//遍历所有边
int a=e[j].a,b=e[j].b,w=e[j].w;
dist[b]=min(dist[b],back[a]+w);//使用backup:避免给a更新后立马更新b,这样b一次性最短路径就多了两条边出来
}
}
if(dist[n]>0x3f3f3f3f/2) return -1;
else 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);
e[i]={a,b,w};
}
int res=bellman_ford();
if(res==-1) puts("impossible");
else cout<<res;
return 0;
}
这个是acwing的一片题解,但是看不懂:
CPPif(dist[n]>0x3f3f3f3f/2) return -1;
这句代码为什么是判断大于0x3f3f3f3f/2?
为啥改成dis[n]==0x3f3f3f3f就过不了了?
回复
共 4 条回复,欢迎继续交流。
正在加载回复...