求救，除了判0的点其他的全错（2.3.9MLE，5.6.8.10.11WA）

gjh303987897 @ 2019-08-28 11:52:21

#include<bits/stdc++.h>
#define maxn 10001
using namespace std;
priority_queue<pair<int ,int> >q;
inline int read()
{
    int x=0; int f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') 
    {
        if(ch=='-')
        {
            f=-1;
        }
        ch=getchar();
    }
    while(ch<='9'&&ch>='0')
    {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
struct data
{
    int dis;
    int to;
    int next;
}a[100010];
int n,m,b;
int fa[maxn],f[maxn];
int bs,head[maxn];
int er[maxn],ans;
inline void add(int x,int y,int z)
{
    bs++;
    a[bs].dis=head[x];   
    a[bs].dis=z;
    a[bs].to=y;
    head[x]=bs;
}
int dist[maxn];
int flag[maxn];
int cheak(int fy)
{
    memset(dist,100000000,sizeof(dist));
    for(int i=1;i<=n;i++)
    {
        if(er[i]>fy) flag[i]=1;
    }
    dist[1]=0;
    q.push(make_pair(0,1));
    while(q.size())
    {
        int x=q.top().second;q.pop();
        if(flag[x]==1) continue;
        flag[x]=1;
        for(int i=head[x];i!=0;i=a[i].next)
        {
            int y=a[i].next; int z=a[i].dis;
            if(dist[y]>dist[x]+z)
            {
                dist[y]>dist[x]+z;
                q.push(make_pair(-dist[y],y));
            }
        }
    }
    if(dist[n]>b)
    {
        return 2;
    }else
    {
        return 1;
    }
}
int find(int x)
{
    if(fa[x]!=x)
    {
        fa[x]=find(fa[x]);
    }
    return fa[x];
}
int main()
{
    n=read(); m=read(); b=read();
    for(int i=1;i<=n;i++)
    {
        f[i]=read();
        er[i]=f[i];
    }
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        x=read(); y=read(); z=read();
        add(x,y,z);
        add(y,x,z);
        fa[y]=x;
    }
    int c1=find(1);
    int c2=find(n);
    if(c1!=c2)
    {
        cout<<"AFK";
        return 0;
    }
    sort(er+1,er+1+n);
    int r=n,l=1;
    int mid=(l+r)>>1;
    while(l<=r)
    {
        if(cheak(er[mid])==2)//no
        {
            r=mid-1;
            mid=(l+r)>>1;
        }else
        {
            ans=mid;
            l=mid+1;
            mid=(l+r)>>1;
        }
    }
    cout<<er[ans];
    return 0;
}

by 常青藤 @ 2019-08-28 12:44:12

貌似还要在读入边时加上

if(x==y) continue;

by gjh303987897 @ 2019-08-28 18:13:21

@常青藤 谢谢了

by gjh303987897 @ 2019-08-28 23:45:05

各位大佬我改了一遍还是一样（蓝瘦香菇）

#include<bits/stdc++.h>
using namespace std;
priority_queue<pair<int,int> >q;
inline int read()
{
    int f=1,x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            f=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
struct data
{
    int dis;
    int to;
    int next;
}a[200001];
int n,m,b;
int er[10001],fy[10001];
int bf[10001];
int bs,head[50020];
inline void add(int x,int y,int z)
{
    bs++;
    a[bs].next=head[x];
    a[bs].to=y;
    a[bs].dis=z;
    head[x]=bs;
}
int dist[50020],flag[50020];
int cheak(int pd)
{
    if(pd<fy[1]||pd<fy[n]) return 1;
    memset(dist,0x3f,sizeof(dist));
    for(register int i=1;i<=n;i++)
    {
        if(fy[i]>pd) flag[i]=1;
    }
    dist[1]=0;
    q.push(make_pair(0,1));
    while(q.size())
    {
        int x=q.top().second;q.pop();
        if(flag[x]==1) continue;
        flag[x]=1;
        for(register int i=head[x];i!=0;i=a[i].next)
        {
            int y=a[i].to;int z=a[i].dis;
            if(dist[y]>dist[x]+z)
            {
                dist[y]=dist[x]+z;
                q.push(make_pair(-dist[y],y));
            }
        }
    }
    if(dist[n]>b) return 1;
    else return 2;
}

inline int find(int po)
{
    if(bf[po]!=po)
    {
        bf[po]=find(bf[po]);
    }
    return bf[po];
}

int main()
{
    n=read(); m=read(); b=read();
    for(register int i=1;i<=n;i++) bf[i]=i;
    for(register int i=1;i<=n;i++)
    {
        fy[i]=read();
        er[i]=fy[i];
    }
    for(register int i=1;i<=m;i++)
    {
        int x,y,z;
        x=read(); y=read(); z=read();
        add(x,y,z);add(y,x,z);
        bf[y]=x;
    }
    if(find(1)!=find(n))
    {
        cout<<"AFK";
        return 0;
    }
    sort(er+1,er+1+n);
    int l=1,r=n;
    int mid=(l+r)>>1;
    while(l<=r)
    {
        if(cheak(mid)==1)
        {
            l=mid+1;
            mid=(l+r)>>1;
        }else
        {
            r=mid-1;
            mid=(l+r)>>1;
        }
    }
    cout<<er[mid];
    return 0;
}