求助大佬，wa了8个点，怎么检查都出不来

我爱杨帆 @ 2020-08-15 09:53:19

#include<bits/stdc++.h>
using namespace std;
struct node
{
    long long v;
    long long id;
    bool operator<(const node &X) const
    {
        return v>X.v;
    }
};
struct node1
{
    long long vv;
    long long hp;
};
priority_queue<node> q;
vector<node1> a[10005];
long long dis[10005],w[10005],maxn=-1;
bool vis[10005];
long long n,m,b,ai,bi,ci;
int check(long long x)
{   
    if(w[1]>x) 
    return 0;
    for(long long i=1;i<=n;i++)
     {
     dis[i]=1e18;
     vis[i]=0;
     }
     dis[1]=0;
     q.push((node){0,1});
   while(!q.empty())
   {
    node t=q.top();
    q.pop();
    long long  now=t.id,d=dis[now];
    if(vis[now]) continue; 
    vis[now]=1;
    for(long long  i=0;i<a[now].size();i++)
     {
       if(vis[a[now][i].vv]) continue;
       if(w[a[now][i].vv]>x) continue;  
       if(dis[a[now][i].vv]>dis[now]+a[now][i].hp)  
        {
         dis[a[now][i].vv]=dis[now]+a[now][i].hp;
         q.push((node){dis[a[now][i].vv],a[now][i].vv});
        }
       if(a[now][i].vv==n)
       {
        if(dis[n]>=b)
        {
        return 0;
        }
        else return 1;
       }    
     }    
   }    
   return 0;        
}
int main()
{  
   cin>>n>>m>>b;
   for(long long i=1;i<=n;i++)
   {
   cin>>w[i];
   maxn=max(maxn,w[i]);
   }
   sort(w+1,w+1+n);
   for(long long i=1;i<=m;i++)
   {
    cin>>ai>>bi>>ci;
    a[ai].push_back((node1){bi,ci});
    a[bi].push_back((node1){ai,ci});
   }
   for(long long i=1;i<=n;i++)
   dis[i]=1e11;
   dis[1]=0; 
   long long l=1,r=maxn,ans=-1;
   while(l<=r)
   {
    long long mid=(l+r)/2;
    if(check(mid))
    ans=mid,r=mid-1;
    else 
    l=mid+1;
   }
   if(ans==-1)
   cout<<"AFK";
   else 
   cout<<ans;
}

by 我爱杨帆 @ 2020-08-15 10:09:47

新版代码

#include<bits/stdc++.h>
using namespace std;
struct node
{
    long long v;
    long long id;
    bool operator<(const node &X) const
    {
        return v>X.v;
    }
};
struct node1
{
    long long vv;
    long long hp;
};
priority_queue<node> q;
vector<node1> a[10005];
long long dis[10005],w[10005],maxn=-1;
bool vis[10005];
long long n,m,b,ai,bi,ci;
int check(long long x)
{   
    if(w[1]>x) 
    return 0;
    for(long long i=1;i<=n;i++)
     {
     dis[i]=1e18;
     vis[i]=0;
     }
     dis[1]=0;
     q.push((node){0,1});
   while(!q.empty())
   {
    node t=q.top();
    q.pop();
    long long  now=t.id,d=dis[now];
    if(vis[now]) continue; 
    vis[now]=1;
    for(long long  i=0;i<a[now].size();i++)
     {
       if(vis[a[now][i].vv]) continue;
       if(w[a[now][i].vv]>x) continue;  
       if(dis[a[now][i].vv]>dis[now]+a[now][i].hp)  
        {
         dis[a[now][i].vv]=dis[now]+a[now][i].hp;
         q.push((node){dis[a[now][i].vv],a[now][i].vv});
        }
       if(a[now][i].vv==n)
       {
        if(dis[n]>=b)
        {
        return 0;
        }
        else return 1;
       }    
     }    
   }    
   return 0;        
}
int main()
{  
   cin>>n>>m>>b;
   for(long long i=1;i<=n;i++)
   {
   cin>>w[i];
   maxn=max(maxn,w[i]);
   }
   for(long long i=1;i<=m;i++)
   {
    cin>>ai>>bi>>ci;
    a[ai].push_back((node1){bi,ci});
    a[bi].push_back((node1){ai,ci});
   }
   for(long long i=1;i<=n;i++)
   dis[i]=1e11;
   dis[1]=0; 
   long long l=1,r=maxn,ans=-1;
   while(l<=r)
   {
    long long mid=(l+r)/2;
    if(check(mid))
    ans=mid,r=mid-1;
    else 
    l=mid+1;
   }
   cout<<ans;
}

by 我爱杨帆 @ 2020-08-15 10:10:12

第十个点还是哇了