题目大意：
一个n个点，m条边的图，每个边有一个边权，每个点也有一个点权。
现在要找一条从1到n的路径，保证边权和不超过b的情况下，最大点权尽量小。
问最大点权最小能是多少？
思路：
二分答案，然后Dijkstra跑最短路判断可行性。
假设二分到的最大点权为m，那么最短路中跑到点权>m的直接忽略，对于长度大于b的最短路也直接忽略。
对点权离散化后二分会快不少。
#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
#include<functional>
#include<ext/pb_ds/priority_queue.hpp>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'';
while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');
return x;
}
const int inf=0x7fffffff;
const int N=;
int f[N],n,m,b;
struct Edge {
int to,w;
};
std::vector<Edge> e[N];
inline void add_edge(const int &u,const int &v,const int &w) {
e[u].push_back((Edge){v,w});
e[v].push_back((Edge){u,w});
}
int d[N];
struct Vertex {
int id,dis;
bool operator > (const Vertex &another) const {
return dis>another.dis;
}
};
__gnu_pbds::priority_queue<Vertex,std::greater<Vertex> > q;
__gnu_pbds::priority_queue<Vertex,std::greater<Vertex> >::point_iterator p[N];
inline void dijkstra(const int &m) {
p[]=q.push((Vertex){});
for(register int i=;i<=n;i++) {
p[i]=q.push((Vertex){i,d[i]=b+});
}
while(q.top().dis<=b) {
const int x=q.top().id;
for(register unsigned i=;i<e[x].size();i++) {
const int &y=e[x][i].to;
if(f[y]>m) continue;
if(d[x]+e[x][i].w<d[y]) {
q.modify(p[y],(Vertex){y,d[y]=d[x]+e[x][i].w});
}
}
q.modify(p[x],(Vertex){,b+});
}
q.clear();
}
inline bool check(const int &m) {
dijkstra(m);
return d[n]!=b+;
}
int v[N];
int main() {
n=getint(),m=getint(),b=getint();
for(register int i=;i<=n;i++) {
v[i]=f[i]=getint();
}
v[]=inf;
std::sort(&v[],&v[n+]);
for(register int i=;i<=m;i++) {
const int &u=getint(),&v=getint(),&w=getint();
add_edge(u,v,w);
}
int l=std::lower_bound(&v[],&v[n+],std::max(f[],f[n]))-v,r=n;
while(l<r) {
const int mid=(l+r)>>;
if(check(v[mid])) {
r=mid;
} else {
l=mid+;
}
}
if(r!=n) {
printf("%d\n",v[r]);
} else {
puts("AFK");
}
return ;
}