【题解】
二分+dijkstra
二分需要交的过路费，然后跑dijkstra判断最短路是否小于s
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define LL long long 5 #define rg register 6 #define N 10010 7 using namespace std; 8 int n,m,st,ed,s,tot,fa,son,last[N],pos[N],f[N],b[N]; 9 LL dis[N]; 10 struct edge{int to,pre,w;}e[100010]; 11 struct rec{int u,v,w;}r[50010]; 12 struct heap{int p;LL d;}h[N]; 13 inline int read(){ 14 int k=0,f=1; char c=getchar(); 15 while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 16 while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar(); 17 return k*f; 18 } 19 inline void up(int x){ 20 while((fa=x>>1)&&h[fa].d>h[x].d) swap(h[fa],h[x]),swap(pos[h[fa].p],pos[h[x].p]),x=fa; 21 } 22 inline void down(int x){ 23 while((son=x<<1)<=tot){ 24 if(h[son].d>h[son+1].d&&son<tot) son++; 25 if(h[son].d<h[x].d) swap(h[son],h[x]),swap(pos[h[son].p],pos[h[x].p]),x=son; 26 else return; 27 } 28 } 29 inline void dijkstra(int x){ 30 for(rg int i=1;i<=n;i++) dis[i]=1e17; 31 h[pos[x]=tot=1]=(heap){x,dis[x]=0}; 32 while(tot){ 33 int now=h[1].p; pos[h[tot].p]=1; h[1]=h[tot--]; if(tot) down(1); 34 for(rg int i=last[now],to;i;i=e[i].pre)if(dis[to=e[i].to]>dis[now]+e[i].w){ 35 dis[to]=dis[now]+e[i].w; 36 if(!pos[to]) h[pos[to]=++tot]=(heap){to,dis[to]}; 37 else h[pos[to]].d=dis[to]; 38 up(pos[to]); 39 } 40 } 41 } 42 inline bool check(int x){ 43 memset(last,0,sizeof(last)); 44 memset(pos,0,sizeof(pos)); 45 tot=0; 46 for(rg int i=1;i<=m;i++){ 47 int u=r[i].u,v=r[i].v,w=r[i].w; 48 if(f[u]<=x&&f[v]<=x){ 49 e[++tot]=(edge){u,last[v],w}; last[v]=tot; 50 e[++tot]=(edge){v,last[u],w}; last[u]=tot; 51 } 52 } 53 dijkstra(st); 54 if(dis[ed]<=s) return 1; 55 return 0; 56 } 57 int main(){ 58 n=read(); m=read(); st=read(); ed=read(); s=read(); 59 for(rg int i=1;i<=n;i++) f[i]=b[i]=read(); 60 sort(b+1,b+1+n); 61 for(rg int i=1;i<=m;i++) r[i].u=read(),r[i].v=read(),r[i].w=read(); 62 int l=0,r=n+1; 63 while(l+1<r){ 64 int mid=(l+r)>>1; 65 if(check(b[mid])) r=mid; else l=mid; 66 } 67 printf("%d ",(r==n+1)?-1:b[r]); 68 return 0; 69 }