感觉，要二分最大收费权的城市，把小于等于它的全部插进去，Dijkstra一下求出最小的血量。这样感觉太暴力了。

考虑只有10000个城市，sort一下，每条无向边都由排名靠后的城市插入。按收费顺序插入城市，直到并查集中1和n连通，来一次Dijkstra求出所需的血量。

假如所需血量已经>=b，说明不合法。

这个时候插入下一个城市及其连通的边，考虑会发生什么改变？首先到达这个城市的最短距离必定是从连出城市走对应路径过来的。

其次它可能会对整个图进行一次更新。所以这个复杂度也是惊人。

所以还是二分城市，要log1e5=15，插入对应的边5e4，跑一次Dijkstra要5e4log5e4=8e5，小得很。

---

想着至少要过一半吧，没想到一发就全AC了。

#include
    
     using namespace std;typedef long long ll;const int MAXN = 1e4 + 5, INF = 0x3f3f3f3f;struct Edge {    int v, w;    Edge() {}    Edge(int v, int w): v(v), w(w) {}};bool vis[MAXN];int dis[MAXN];vector
     
       G[MAXN];int fa[MAXN];int find(int x) {    return fa[x] == x ? x : fa[x] = find(fa[x]);}void merge(int x, int y) {    int fx = find(x), fy = find(y);    fa[fy] = fx;}struct City {    int id, f;    bool operator<(const City &c)const {        return f < c.f;    }} city[MAXN];int n, b;void Init() {    for(int i = 0; i <= n; ++i)        fa[i] = i;    memset(vis, 1, sizeof(vis[0]) * (n + 1));    memset(dis, INF, sizeof(dis[0]) * (n + 1));}void AddCity(int Ceil) {    for(int i = 1; i <= Ceil; ++i) {        int u = city[i].id;        vis[u] = 0;        for(auto ei : G[u])            merge(u, ei.v);    }}priority_queue
      
       
         > pq;int Dijkstra(int s) {    pq.push({0, 1});    dis[1] = 0;    while(!pq.empty()) {        int u = pq.top().second;        pq.pop();        if(vis[u])            continue;        vis[u] = 1;        for(auto ei : G[u]) {            int v = ei.v, w = ei.w;            if(!vis[v] && dis[u] + w < dis[v]) {                dis[v] = dis[u] + w;                pq.push({-dis[v], v});            }        }    }    return dis[n];}bool check(int Ceil) {    Init();    AddCity(Ceil);    if(find(1) != find(n))        return false;    int res = Dijkstra(1);    return res < b;}int main() {#ifdef Yinku    freopen("Yinku.in", "r", stdin);#endif // Yinku    int m;    scanf("%d%d%d", &n, &m, &b);    for(int i = 1; i <= n; ++i) {        scanf("%d", &city[i].f);        city[i].id = i;    }    sort(city + 1, city + 1 + n);    for(int i = 1; i <= m; ++i) {        int u, v, w;        scanf("%d%d%d", &u, &v, &w);        G[u].emplace_back(Edge(v, w));        G[v].emplace_back(Edge(u, w));    }    int L = 1, R = n, M;    while(1) {        M = L + R >> 1;        if(L == M) {            if(check(L)) {                printf("%d\n", city[L].f);                return 0;            } else if(check(R)) {                printf("%d\n", city[R].f);                return 0;            }            puts("AFK");            return 0;        }        if(check(M))            R = M;        else            L = M + 1;    }}