题解 | #游游出游#

二分+dijk算法

#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <stack>
#include <numeric>
#include <ctime>
#include <string>
#include <bitset>
#include <unordered_map>
#include <unordered_set>

using namespace std;
using ll = long long;

const ll N = 5e5 + 5, mod = 1e9 + 7, inf = 2e18;
const double esp = 1e-8;

int n, m, h;

struct Node {
    ll v, w, z;
};

vector<Node>g[N];
bool vis[N];
ll dis[N];

struct node {
    ll id, vlu;
    bool operator<(const node& u)const {
        return u.vlu < vlu;
    }
};

bool dijk(int mid) {
    for (int i = 0; i <= n + 3; i++) {
        dis[i] = inf;
        vis[i] = false;
    }

    priority_queue<node>pq;

    pq.push({1, dis[1] = 0});

    while (!pq.empty()) {
        node tem = pq.top();
        pq.pop();

        if (vis[tem.id])continue;
        vis[tem.id] = true;

        for (auto [y, w, z] : g[tem.id]) {
            if (dis[y] > dis[tem.id] + z && w >= mid) {
                pq.push({y, dis[y] = dis[tem.id] + z});
            }
        }
    }

    return dis[n] <= h;
}


void solve() {
    cin >> n >> m >> h;

    while (m--) {
        ll u, v, w, z;
        cin >> u >> v >> w >> z;
        g[v].push_back({u, w, z});
        g[u].push_back({v, w, z});
    }

    ll l = 0, r = 1e9 + 5, ans = inf;

    while (l <= r) {
        ll mid = l + r >> 1;

        if (dijk(mid)) {
            l = mid + 1;
            ans = mid;
        } else {
            r = mid - 1;
        }
    }
    cout << (ans == inf ? -1 : ans);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t = 1;
    //cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}