#include<bits/stdc++.h>using namespace std;int n,m,b,cnt,ans;int f[1000000],c[1000000],nxt[1000000],to[1000000],val[1000000];int dis[1000000],head[1000000];int xx=1000000000,yy=0;void add(int x,int y,int z){ cnt++; nxt[cnt]=head[x]; head[x]=cnt; to[cnt]=y; val[cnt]=z;}bool spfa(int mid){ if(mid<f[1])return false; queue<int> q; memset(dis,0x3f,sizeof(dis)); bool ff[10000]; dis[1]=0; ff[1]=true;q.push(1); while(q.size()) { int a=q.front();q.pop();ff[a]=false; for(int i=head[a];i!=0;i=nxt[i]) { if(f[to[i]]<=mid&&dis[to[i]]>dis[a]+val[i]) { dis[to[i]]=dis[a]+val[i]; if(!ff[to[i]]) { ff[to[i]]=true; q.push(to[i]); } } } } if(dis[n]<=b)return true; else return false;}int main(){ scanf("%d%d%d",&n,&m,&b); for(int i=1;i<=n;i++) { scanf("%d",&f[i]); yy=max(yy,f[i]); xx=min(xx,f[i]); } int x,y,z; for(int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); } while(xx<=yy) { int mid=(xx+yy)>>1; if(spfa(mid)) { ans=mid; yy=mid-1; } else xx=mid+1; } if(ans)cout<<ans; else cout<<"AFK"; return 0;}
转载于:https://www.cnblogs.com/647Z/p/7356187.html
相关资源：JAVA上百实例源码以及开源项目