洛谷P1462 通往奥格瑞玛的道路题解最短路+二分答案

题目链接：https://www.luogu.com.cn/problem/P1462

题目大意：

有 \(n\) 个点 \(m\) 条边，每个点有一个点权，每个边有一个边权。求所有长度不超过 \(b\) 的路径中的点权最大值的最小值。

解题思路：

二分答案 \(D\)（即点权最小值），每次求最短路查看有没有所有点权都 \(\le D\) 的最短路径长度 \(\le b\)。

实现代码如下：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 10010;

int n, m;

long long b, f[maxn];

struct Node {

    int v, w;

    Node () {};

    Node (int _v, int _w) { v = _v; w = _w; }

};

vector<Node> g[maxn];

queue<int> que;

long long dist[maxn];

bool inq[maxn];

bool check(long long D) { // SPFA

    for (int i = 1; i <= n; i ++) {

        dist[i] = -1;

        inq[i] = false;

    }

    while (!que.empty()) que.pop();

    dist[1] = 0;

    que.push(1);

    while (!que.empty()) {

        int u = que.front();

        que.pop();

        inq[u] = false;

        int sz = g[u].size();

        for (int i = 0; i < sz; i ++) {

            int v = g[u][i].v, w = g[u][i].w;

            if (f[v] > D) continue;     // 城市收取费用不能超过D

            if (dist[u] + w > b) continue;  // 距离不能超过b

            if (dist[v] == -1 || dist[v] > dist[u] + w) {

                dist[v] = dist[u] + w;

                if (!inq[v]) {

                    inq[v] = true;

                    que.push(v);

                }

            }

        }

    }

    return dist[n] != -1 && dist[n] <= b;

}

void solve() {

    long long L = 0, R = 0, res = -1;

    for (int i = 1; i <= n; i ++) R = max(R, f[i]);

    while (L <= R) {

        long long mid = (L + R) / 2;

        if (check(mid)) {

            res = mid;

            R = mid - 1;

        }

        else L = mid + 1;

    }

    if (res == -1) puts("AFK");

    else cout << res << endl;

}

int main() {

    cin >> n >> m >> b;

    for (int i = 1; i <= n; i ++) cin >> f[i];

    while (m --) {

        int u, v;

        long long w;

        cin >> u >> v >> w;

        g[u].push_back(Node(v, w));

        g[v].push_back(Node(u, w));

    }

    solve();

    return 0;

}

巴特西

洛谷P1462 通往奥格瑞玛的道路题解最短路+二分答案

最新文章

热门文章

巴特西

洛谷P1462 通往奥格瑞玛的道路 题解 最短路+二分答案

最新文章

热门文章

洛谷P1462 通往奥格瑞玛的道路题解最短路+二分答案