是否有两次 Dijkstra 解法？

首先第一次 Dijkstra 求出每个结点所需要消耗的最小血量，即求出可否到达这个结点。

第二次 Dijkstra 是在可以到达的结点中跑最短路，注意这里求的是路径中最大值（这个应该是可以 Dijkstra 的）。

最后答案即为第二次 Dijkstra 的 $d_n$。

样例可过，hack 可过，但 WA 90。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 10001

int n, m, b, u, v, w;
int f[MAXN], minn[MAXN], dis[MAXN];
vector<pair<int, int>> e[MAXN];
bitset<MAXN> vis;

struct Node{
    int u, dis;
    bool operator<(Node b)const{
        return dis > b.dis;
    }
};
priority_queue<Node> pq;

void dijkstra1(){
    minn[1] = 0;
    pq.push({1, 0});
    while (!pq.empty()){
        u = pq.top().u;
        pq.pop();
        if (vis.test(u)) continue;
        vis.set(u);

        for (auto i: e[u]){
            v = i.first;
            w = i.second;
            if (minn[v] > minn[u] + w){
                minn[v] = minn[u] + w;
                pq.push({v, minn[v]});
            }
        }
    }
}

void dijkstra2(){
    dis[1] = f[1];
    pq.push({1, 0});
    while (!pq.empty()){
        u = pq.top().u;
        pq.pop();
        if (vis.test(u)) continue;
        vis.set(u);

        for (auto i: e[u]){
            v = i.first;
            if (minn[v] <= b && dis[v] > max(dis[u], f[v])){
                dis[v] = max(dis[u], f[v]);
                pq.push({v, dis[v]});
            }
        }
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> b;
    for (int i(1); i<=n; ++i) cin >> f[i];
    while (m--){
        cin >> u >> v >> w;
        e[u].push_back(make_pair(v, w));
        e[v].push_back(make_pair(u, w));
    }

    memset(minn, 0x3f, sizeof(minn));
    dijkstra1();

    memset(dis, 0x3f, sizeof(dis));
    vis.reset();
    dijkstra2();

    if (dis[n] == 0x3f3f3f3f3f3f3f3f) cout << "AFK";
    else cout << dis[n];

    return 0;
}