孩子快疯了，有大佬帮忙看看我spfa错哪里了吗

weconyed @ 2022-10-31 23:10:47

#include<bits/stdc++.h>
using namespace std;
long long n,m,b;

long long f[10005];

struct ed{
    long long to,nxt,val;
}e[100005];

long long head[10005],cnt=0;

void add(long long x,long long y,long long v){
    e[++cnt].to=y;
    e[cnt].nxt=head[x];
    e[cnt].val=v;
    head[x]=cnt; 
}

long long dis[10005],st[10005];
queue<long long> qu;
long long spfa(long long fm){
    memset(dis,0x3f3f3f,sizeof(dis));
    dis[1]=0,st[1]=1;
    qu.push(1);
    while(!qu.empty()){
        long long tmp=qu.front();
        qu.pop();
        st[tmp]=0;
        for(long long i=head[tmp];i;i=e[i].nxt){
            long long y=e[i].to;
            if(dis[tmp]+e[i].val<dis[y]){
                dis[y]=dis[tmp]+e[i].val;
                if(!st[y]&&f[y]<=fm){
                    qu.push(y);
                    st[y]=1;
                }
            }   
        }
    }
    if(dis[n]>=b) return 0;
    else return 1;
}
int main(){
    cin>>n>>m>>b;
    long long l,r=0;
    for(long long i=1;i<=n;i++){
        cin>>f[i];
        r=max(f[i],r);
    }
    l=max(f[1],f[n]);
    for(long long i=1;i<=n;i++){
        long long x,y,v;
        cin>>x>>y>>v;
        if(x==y) continue;
        add(x,y,v);
        add(y,x,v);
    }
    if(!spfa(2000000005)){
        cout<<"AFK";
        return 0;
    }
    //if(!spfa(723502837))  cout<<"mdzz";
    while(l<=r){
        long long mid=(l+r)/2;
        if(spfa(mid)) r=mid-1;
        else l=mid+1;
    }
    cout<<l;
    return 0;
} 

by DEMAC @ 2022-10-31 23:23:05

你的memset是不是少打了一个3f?

0x3f3f3f=4144959

0x3f3f3f3f=1061109567

by hegm @ 2022-11-01 06:36:43

@weconyed memset 里面的数改成 0x3f

by hegm @ 2022-11-01 06:59:06

@weconyed 错误挺多的

by hegm @ 2022-11-01 07:02:47

1. 一共有 m 条边，你读了 n 条边
2. spfa$ 更新的时候必须要保证 $dis[tmp]+e[i].val<dis[y]$ **和** $f[y]<=fm

应写为

if(dis[tmp]+e[i].val<dis[y]&&f[y]<=fm)
{
        dis[y]=dis[tmp]+e[i].val;
       if(!st[y])
       {
               qu.push(y);
        st[y]=1;
    }
}

by hegm @ 2022-11-01 07:03:05

az,代码有点乱

by hegm @ 2022-11-01 07:03:40

给你放个全部的

#include<bits/stdc++.h>
using namespace std;
long long n,m,b;

long long f[10005];

struct ed{
    long long to,nxt,val;
}e[100005];

long long head[10005],cnt=0;

void add(long long x,long long y,long long v){
    e[++cnt].to=y;
    e[cnt].nxt=head[x];
    e[cnt].val=v;
    head[x]=cnt; 
}

long long dis[10005],st[10005];
queue<long long> qu;
long long spfa(long long fm){
    for(int i=1;i<=n;i++)dis[i]=10000000000008;
    memset(st,0,sizeof(st)); 
    if(fm<f[1])return 0;
    dis[1]=0,st[1]=1;
    qu.push(1);
    while(!qu.empty()){
        long long tmp=qu.front();
        qu.pop();
        st[tmp]=0;
        for(long long i=head[tmp];i;i=e[i].nxt){
            long long y=e[i].to;
            if(dis[tmp]+e[i].val<dis[y]&&f[y]<=fm){
                dis[y]=dis[tmp]+e[i].val;
                if(!st[y])
                {
                    qu.push(y);
                    st[y]=1;
                }
            }   
        }
    }
    if(dis[n]>b) return 0;
    else return 1;
}
int main(){
    cin>>n>>m>>b;
    long long l,r=0;
    for(long long i=1;i<=n;i++){
        cin>>f[i];
    }
    for(long long i=1;i<=m;i++){
        long long x,y,v;
        cin>>x>>y>>v;
        if(x==y) continue;
        add(x,y,v);
        add(y,x,v);
    }
    if(!spfa(10000000000000008)){
        cout<<"AFK";
        return 0;
    }
    l=0,r=10000000006;
    while(l<=r){
        long long mid=(l+r)/2;
        if(spfa(mid)) r=mid-1;
        else l=mid+1;
    }
    cout<<l; 
    return 0;
} 

by weconyed @ 2022-11-03 21:54:51

@hegm 谢谢哥，你是我亲哥（/泪）

by hegm @ 2022-11-04 06:50:59

@weconyed 给个关注呗，亲弟弟，