求助。样例输出一直是6,查不出问题..

P1462 通往奥格瑞玛的道路

henry_y @ 2018-03-20 22:18:50

如题,各种修改之后一直都是输出6,哪位dalao帮忙看一下啊(感激不尽.jpg)

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define maxn 100100
#define inf 1<<30
#define mt(x,y) memset(x,y,sizeof(x))
#define max(x,y) x>y?x:y
#define min(x,y) x<y?x:y
#define abs(x) x>0?x:-x
#define mod 10000007
#define lowbit(x) x&-x
inline void read(int &x){x=0;int f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;}
using namespace std;
struct edge{int to,next,v;}e[maxn];
int head[maxn],cnt=1;
int n,m,b;
int f[maxn],p[maxn],vi[maxn],d[maxn],q[maxn];
inline void add(int u,int v,int w){e[++cnt].to=v;e[cnt].next=head[u];e[cnt].v=w;head[u]=cnt;}
inline void Add(int u,int v,int w){add(u,v,w);add(v,u,w);}
inline bool spfa(int top){
    mt(vi,0);mt(d,inf);
    int l=1,r=2,u,v;
    q[1]=1;vi[1]=1;d[1]=0;
    while(l<r){
        u=q[l++];vi[u]=0;
        for(int i=head[u];i;i=e[i].next){
            v=e[i].to;
            if(e[i].v+d[u]<d[v]&&f[e[i].to]<=top){
                d[v]=e[i].v+d[u];
                if(!vi[v]){
                    vi[v]=1;
                    q[r++]=v;
                }
            }
        }
    }
    if(d[n]<=b)return 1;
    else return 0;
}
int main(){
    read(n);read(m);read(b);int u,v,w;
    for(int i=1;i<=n;i++){read(f[i]);p[i]=f[i];}
    for(int i=1;i<=m;i++){
        read(u);read(v);read(w);
        Add(u,v,w);
    }sort(p+1,p+n+1);
    int l=1,r=n,mid,ans=-1;
    while(l<r){
        mid=(l+r)/2;
        if(spfa(p[mid])){
            ans=p[mid];
            r=mid-1;
        }else l=mid+1;
    }
    if(ans==-1)printf("AFK");
    else printf("%d",ans);
    return 0;
}

by FrenzyHydra @ 2018-04-19 21:33:35

二分应该l<=r 我不会告诉你我这个错查了一天~~~~


|