73pts 求助

WA #1 #4 #7

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,b,maxn;
int head[N],to[N<<1],nxt[N<<1],w[N<<1],cnt=1;
int cost[N],d[N],v[N];
priority_queue<pair<int,int> >q;
void add(int u,int v,int e){
   to[cnt]=v;
   w[cnt]=e;
   nxt[cnt]=head[u];
   head[u]=cnt++;
}
void dij(){
   memset(d,0x3f,sizeof d);
   d[1]=0;
   q.push(make_pair(0,1));
   while(q.size()){
      int x=q.top().second;q.pop();
      if(v[x]) continue;
      v[x]=1;
      for(int i=head[x];i;i=nxt[i]){
         int y=to[i],z=w[i];
         if(d[y]>d[x]+z){
            d[y]=d[x]+z;
            q.push(make_pair(-d[y],y));
         }
      }
   }
}
bool check(int x){
   memset(v,0,sizeof v);
   for(int i=1;i<=n;i++)
      if(cost[i]>x) v[i]=1;
   if(v[n]) return 0;
   // for(int i=1;i<=n;i++)
   //    cout<<v[i]<<" ";
   // cout<<endl;
   dij();
   // cout<<d[n]<<endl;
   if(d[n]<b) return 1;
   return 0;
}
int main(){
   ios::sync_with_stdio(0);
   cin>>n>>m>>b;
   for(int i=1;i<=n;i++) cin>>cost[i],maxn=max(maxn,cost[i]);
   for(int i=1,u,v,w;i<=m;i++){
      cin>>u>>v>>w;
      add(u,v,w),add(v,u,w);
   }
   int l=1,r=maxn;
   while(l+1<r){
      int mid=(l+r)>>1;
      if(check(mid)) r=mid;
      else l=mid;
   }
   cout<<r;
   return 0;
}