SPFA初始化d[]数组的大小时,INF的大小好玄学!

P1462 通往奥格瑞玛的道路

currycodingg @ 2018-07-13 23:51:44

各位神犇们帮忙看一下好吗,就是一句话的事,导致我从WA了九个点到AC......

#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring> 
#include<algorithm>
using namespace std;
const int N=10000+3;
const int M=50000+3;
const int INF=2147483646;
struct edge{
    int v,c,next;//c为血量 
}e[M*2];
int n,m,b,head[N],cnt,f[N],ff[N],d[N];//f[i]为费用(点权) ,d[i]为耗血(距离) 
bool inq[N];

void addedge(int from,int to,int len){
    e[++cnt]=(edge){to,len,head[from]}; head[from]=cnt;
}

bool SPFA(int topp){
    //就是下面这句话!!!
    //for(int i=1;i<=n;i++) d[i]=INF;// WA了九个点
    memset(d,0x3f3f3f3f,sizeof(d));  //AC!!??
    //这个INF的大小会对结果产生怎样的影响???求神犇指教qwq

    memset(inq,false,sizeof(inq));
    queue<int> Q;
    Q.push(1); inq[1]=true; d[1]=0;

    while(!Q.empty()){
        int u=Q.front(); Q.pop(); inq[u]=false;
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].v,  c=e[i].c;
            if(d[v]>d[u]+c && f[v]<=topp){
                d[v]=d[u]+c; 
                if(!inq[v]){ Q.push(v); inq[v]=true; }
            }
        }
    }
    if(d[n]<=b) return true;
    else return false;
}

int main(){
    scanf("%d%d%d",&n,&m,&b);
    for(int i=1;i<=n;i++){
        scanf("%d",&f[i]); ff[i]=f[i];//SPFA时用f[]   二分时用ff[](先将ff[]排序)  !! 
    } 
    int x,y,z;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        addedge(x,y,z); addedge(y,x,z);
    }

    sort(ff+1,ff+n+1);
    int maxx=ff[n];
    //若点权为最大仍无法满足要求 则 AFK 
    if(SPFA(maxx+100)==false) {
        printf("AFK\n");  return 0;
    }

    int l=1,r=n,mid;
    int ans;
    while(l<=r){        //二分的对象是点权 
        mid=(l+r)>>1;
        if(SPFA(ff[mid])) { ans=ff[mid]; r=mid-1; }
        else l=mid+1;
    }
    printf("%d\n",ans);
    return 0;
} 

多多指教,在下感激不尽qwq


by 小粉兔 @ 2018-07-14 01:05:05

inf设太大会爆int变成负数


by henry_y @ 2018-07-17 19:56:45

你inf设的是int的最大值,然后下面spfa的松弛操作是有加法的,加了就溢出了变成负数

改小一点就没什么问题了,比如1<<30什么的


by coyangjr @ 2018-07-18 14:31:14

推荐

const int INF = 0x3f3f3f3f ;

INF的大小为:1061109567


by wyyXHyzw @ 2018-07-24 12:37:48

如果有两个INF加起来比较会溢出变成负数


by currycodingg @ 2018-07-27 16:42:57

谢谢楼上各位神犇!


|