洛谷P1462 通往奥格瑞玛的道路

题目传送门：https://www.luogu.com.cn/problem/P1462

第一感觉跟leetcode做过的这道题很像，于是采用启发式搜索，取h(x) 恒等于0，很显然启发函数是可接受的、一致的，即Dijkstra。

但是提交了一发只拿到90分，代码如下：

#include <bits/stdc++.h>
using i64 = long long;
using namespace std;
typedef pair<int, int> pii;
constexpr int N = 1e4 + 5, M = 5e4 + 5;
int ver[M << 1], edge[M << 1], nxt[M << 1], head[N], tot;
bool vis[N];
void add(int x, int y, int z) {
    ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
}
struct node {
    int idx, hp, mx;
    node() {}
    node(int idx, int hp, int mx) {
        this->idx = idx;
        this->hp = hp;
        this->mx = mx;
    }
}d[N];
const int inf = 1e9 + 1;
void solve() {
    int n, m, b;
    cin >> n >> m >> b;
    fill(d, d + N, node(0, 0, inf));
    vector<int> f(n+1);
    for (int i = 1; i <= n; ++i) {
        cin >> f[i];
    }
    for (int i = 0; i < m; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z);
        add(y, x, z);
    }
    auto cmp = [](const node &lhs, const node &rhs) {
        return lhs.mx > rhs.mx;
    };
    priority_queue<node, vector<node>, decltype(cmp)> q(cmp);
    d[1] = node(1, b, f[1]);
    q.push(d[1]);
    while (!q.empty()) {
        auto u = q.top(); q.pop();
        int x = u.idx;
        if (vis[x]) continue;
        vis[x] = 1;
        for (int i = head[x]; i ; i = nxt[i]) {
            int y = ver[i], c = edge[i];
            int hp = u.hp - c;
            if (hp < 0) continue;
            int gx = max(d[x].mx, f[y]);
            if (gx < d[y].mx) {
                d[y] = {y, hp, gx};
                q.push(d[y]);
            }
        }
    }
    if (d[n].mx == inf) {
        cout << "AFK\n";
        return;
    }
    cout << d[n].mx << '\n';
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

错在哪里了呢？因为可能最优解可能会因为生命值耗尽而走不到，所以这只是个错误的贪心。

题解区有一句至理名言：一切最值问题都可以二分。

这题也可以用二分来做，二分可走的收费上限（即不走超过收费上限的路），使用dijkstra求最大剩余生命值，根据是否为负判定是否可行。

AC代码如下：

#include <bits/stdc++.h>
using i64 = long long;
using namespace std;
typedef pair<int, int> pii;
constexpr int N = 1e4 + 5, M = 5e4 + 5;
int ver[M << 1], edge[M << 1], nxt[M << 1], head[N], tot;
i64 d[N];
bool vis[N];
void add(int x, int y, int z) {
    ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
}
const i64 inf = 4e18;
void solve() {
    int n, m, b;
    cin >> n >> m >> b;
    vector<int> f(n+1);
    for (int i = 1; i <= n; ++i) {
        cin >> f[i];
    }
    for (int i = 0; i < m; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z);
        add(y, x, z);
    }
    auto judge = [&](int limit) -> bool {
        fill(d + 1, d + 1 + n, inf);
        memset(vis, 0, sizeof vis);
        priority_queue<pair<i64, int>> q;
        if (f[1] > limit) return false;
        d[1] = 0;
        q.push({0, 1});
        while (!q.empty()) {
            auto u = q.top(); q.pop();
            int x = u.second;
            if (vis[x]) continue;
            vis[x] = 1;
            if (x == n) {
                i64 cost = -u.first;
                return cost <= b;
            }
            for (int i = head[x]; i ; i = nxt[i]) {
                int y = ver[i], z = edge[i];
                if (f[y] > limit) continue;
                if (d[x] + z < d[y]) {
                    d[y] = d[x] + z;
                    q.push({-d[y], y});
                }
            }
        }
        return false;
    };
    int mx = *max_element(f.begin(), f.end());
    // 注意端点取不到
    int l = max(f[1], f[n]) - 1, r = mx + 1;
    int ans = -1;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (judge(mid)) {
            r = mid;
            ans = r;
        } else {
            l = mid + 1;
        }
    }
    if (ans == -1 || ans > mx){
        cout << "AFK\n";
        return;
    }
    cout << ans << '\n';
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}