洛谷 P1462 练习

洛谷 P1462 题解

原题链接：P1462 通往奥格瑞玛的道路

1. 做题心得

今天恢复了做题，接着以前的最短路来做。首先声明，我是个小白，看到最大值的最小值，首先想到二分，但是不知道怎么抽了，又觉得二分不能做，我就想先用暴力 DFS 搜出来所有可行的路，维护一个最大值，最后求最小，但是复杂度是指数级的。

后来我又想从贵的点一个一个删除，判断可达，如果用 DFS 或 BFS，复杂度就是 O((m+n)*n)，还是不能过这个题。还有判断可达我又想到了并查集，但是并查集没办法处理路径权重。

最终只能求助 Gemini 大人了，它给了我思路：二分 + Dijkstra。二分的思想是降维，这题有两个维度：第一是血量，第二是花费。把花费限制在 mid 之下，只需判断是否可达，用 Dijkstra 来解决，复杂度为 O(log1e9 * m * logn)。

2. 犯的错误

即使有了思路还是少不了乱七八糟的错误。

2.1 Dijkstra 模板不熟练

找到点竟然忘了入队：

pq.push({dis[nn], nn});

2.2 堆的方向忘了

priority_queue 默认是大顶堆，需要加入 greater<> 来控制堆的方向。

• less<>：大顶堆，较大的先出队
• greater<>：小顶堆，较小的先出队

2.3 memset 的误区

memset 是按字节来赋值的，经常用 0x3f 而不是 1e9。

memset(dis, 0x3f, sizeof(dis));  // 正确
memset(dis, 1e9, sizeof(dis));   // 错误！

2.4 二分边界

int l = -1, r = 1e9 + 1;
while (l + 1 != r) {
    int mid = (l + r) >> 1;
    if (check(mid)) r = mid;
    else l = mid;
}

注意事项：

1. 左右指针最开始不能在范围内
2. l + 1 != r 才是判断条件

2.5 逻辑错误

问题	检查点
起点合不合法？	入队前检查
松弛邻居时，邻居合不合法？	松弛前检查 ← 我漏的
出队时，节点合不合法？	出队时检查

重点：dis 在松弛的时候被更新了，虽然不会拓展新节点，但是检查的时候要检查邻居 f[nn] > li，而不是 f[sn] > li。

禁用节点就要彻底禁用

思考会不会别的地方更新

可以封装函数判断合法性

封装函数判断节点是否可用，不容易遗漏。

3. 源码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e4 + 10;
using PII = pair<long long, long long>;
using ll = long long;

ll n, m, b;
ll f[MAXN], vis[MAXN], dis[MAXN];
vector<vector<PII>> bl(MAXN);

void Dijkstra(ll limit) {
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    dis[1] = 0;
    pq.push({0, 1});
    while (!pq.empty()) {
        auto [sd, sn] = pq.top();
        pq.pop();
        if (vis[sn] || f[sn] > limit) continue;
        vis[sn] = 1;
        for (auto [nd, nn] : bl[sn]) {
            if (vis[nn] || f[nn] > limit) continue;
            if (sd + nd < dis[nn]) {
                dis[nn] = sd + nd;
                pq.push({dis[nn], nn});
            }
        }
    }
}

bool check(ll limit) {
    memset(vis, 0, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));
    Dijkstra(limit);
    return dis[n] <= b;
}

int main() {
    cin >> n >> m >> b;
    for (int i = 1; i <= n; i++) {
        cin >> f[i];
    }
    for (int i = 1; i <= m; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        bl[a].push_back({c, b});
        bl[b].push_back({c, a});
    }

    int l = -1, r = 1e9 + 1;
    while (l + 1 != r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid;
    }

    if (!check(1e9)) cout << "AFK";
    else cout << r;

    return 0;
}

4. 总结

还是要细心，模板背好。其实挺基础一道题，因为各种基础错误导致做不出来。记住：细节决定成败！