社区讨论

关于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的一片题解,但是看不懂:
CPP
if(dist[n]>0x3f3f3f3f/2) return -1;
这句代码为什么是判断大于0x3f3f3f3f/2?
为啥改成dis[n]==0x3f3f3f3f就过不了了?

回复

4 条回复,欢迎继续交流。

正在加载回复...