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
#include
#include
#include
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];
queueq;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;
}

View Ugly Code =w=