QwQ马上高二啦不能颓啦…知乎上听说写博客的效果挺好的，来试一下好啦~
题目描述
在艾泽拉斯，有n个城市。编号为1,2,3,...,n。
城市之间有m条双向的公路，连接着两个城市，从某个城市到另一个城市，会遭到联盟的攻击，进而损失一定的血量。
每次经过一个城市，都会被收取一定的过路费（包括起点和终点）。路上并没有收费站。
假设1为暴风城，n为奥格瑞玛，而他的血量最多为b，出发时他的血量是满的。
歪嘴哦不希望花很多钱，他想知道，在可以到达奥格瑞玛的情况下，他所经过的所有城市中最多的一次收取的费用的最小值是多少。
orz一开始就像其中一个题解一样直接跑两遍spfa，然后是wa掉了一个点（后来看了看题解发现这种方法是错误的（不过居然才wa了一个点…
好叭我最后还是老老实实写了二分（然而这里我又智障了没开long long结果wa了好多次还没发现…）
嗯那么做法就是先跑一边最短路spfa，看一下这种情况下能否到达终点，不能的话直接输出AFK（_(:з」∠)_话说为啥是AFK？）
然后如果可以的话就给f[]排个序对f[]进行二分，如果当前的值太小的话就往大的找否则往小的找（QwQ哦千万不能像我一样一开始还把边集数组开小了…
最后贴上长得不太好看的代码x（代码：喵喵喵？
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int INF=0x7f7f7f7f; const int M=100005; const int N=10005; struct edge{int to,weight,next;}edges[M]; int head[N],cnt; int n,m,b,l,r,ans;long long dis[N]; int f[N],temp[N]; queue<int>q;bool inQ[N]; inline void addEdge(int u,int v,int w) { edges[++cnt]=(edge){v,w,head[u]}; head[u]=cnt; } inline int read() { int s=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){s=s*10+c-'0';c=getchar();} return s*f; } inline bool spfa(int s) { memset(dis,0x7f,sizeof(dis)); memset(inQ,0,sizeof(inQ)); dis[1]=0;inQ[1]=1;q.push(1); while(!q.empty()){ int cur=q.front();q.pop(); inQ[cur]=0; for(int i=head[cur];i;i=edges[i].next) { if(f[edges[i].to]>s)continue; if(dis[edges[i].to]>dis[cur]+edges[i].weight) { dis[edges[i].to]=dis[cur]+edges[i].weight; if(!inQ[edges[i].to]){q.push(edges[i].to);inQ[edges[i].to]=1;} } } } if(dis[n]>=b||dis[n]==dis[0])return 0; return 1; } int main() { n=read();m=read();b=read(); for(int i=1;i<=n;i++)f[i]=temp[i]=read(); for(int i=1;i<=m;i++) { int u,v,w; u=read();v=read();w=read(); addEdge(u,v,w);addEdge(v,u,w); } if(!spfa(INF))printf("AFK"); else{ sort(temp+1,temp+n+1); temp[n+1]=temp[n]+1; l=1;r=n+1; while(r-l>1) { int mid=l+r>>1; if(spfa(temp[mid]))r=mid,ans=temp[mid]; else l=mid; }printf("%d",ans); } return 0; }