导致我WA十几遍的原因居然是最大值不够大……以后再也不相信memset(dis,127/3,sizeof(dis))了。
此题先将花费排序，然后二分最大花费，spfa判断解是否可行。spfa的时候遇到一个大于当前二分的花费的点就跳过。如果起点的点权超过了这个花费，或者最后到达n时的最短路径超过了歪嘴哦的血量，则当前解不可用，l=mid+1.否则记录当前答案，r=mid-1。
代码如下
#include<cstdio> #include<cctype> #include<cstring> #include<cmath> #include<algorithm> using namespace std; inline long long read(){ long long num=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)){ num=num*10+ch-'0'; ch=getchar(); } return num*f; } struct Edge{ int next,to,dis; }edge[1000000]; int head[1000000],num; int dis[200000]; inline void add(int from,int to,int dis){ edge[++num]=(Edge){head[from],to,dis}; head[from]=num; } int que[100000]; int cost[1000000]; int f[1000000],h,t=1; bool vis[200000]; long long ans=-1; int main(){ int n=read(),m=read(),Max=read(); for(int i=1;i<=n;++i){ que[i]=read(); cost[i]=que[i]; } sort(que+1,que+n+1); for(int i=1;i<=m;++i){ int from=read(),to=read(),dst=read(); add(from,to,dst); add(to,from,dst); } int l=1,r=n; while(l<=r){ int mid=(l+r)>>1; for(int i=1;i<=n;++i) dis[i]=1000000000; memset(vis,0,sizeof(vis)); int limit=que[mid]; f[1]=1;h=0;t=1;dis[1]=0; while(h++<t){ vis[f[h]]=0; for(int i=head[f[h]];i;i=edge[i].next){ if(cost[edge[i].to]>limit) continue; if(dis[f[h]]+edge[i].dis<dis[edge[i].to]){ dis[edge[i].to]=dis[f[h]]+edge[i].dis; if(!vis[edge[i].to]){ vis[edge[i].to]=1; f[++t]=edge[i].to; } } } } if(dis[n]>=Max||cost[1]>limit) l=mid+1; else{ ans=que[mid]; r=mid-1; } } if(ans==-1) printf("AFK"); else printf("%lld",ans); return 0; }