知识点1：二分答案

对于一个问题，它的答案属于一个区间，当这个区间很大时，暴力超时。但重要的是——这个区间是对题目中的某个量有单调性的，此时，我们就会二分答案。每一次二分会做一次判断（check函数），看是否对应的那个量达到了需要的大小，如果满足check，就放弃右半区间（或左半区间），如果不满足，就放弃左半区间（或右半区间）。一直往复，直至到最终的答案。

题目求的是车重量的最大值，显然符合单调性。因为随着重量的增加，可选的路径在变少，就有可能无法到达终点。反之，若车重为w时若可以到达终点，那么车重小于w时也必然可以到达终点，因为可选的路径增加了。

知识点2：单源最短路径

给定一个带权有向图 G=(V,E) ，其中每条边的权是一个非负实数。另外，还给定 V 中的一个顶点，称为源。我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。

单源最短路径问题适用的算法是迪杰斯特拉（Dijkstra）算法。它是由荷兰计算机科学家艾兹格·迪科斯彻（Edsger Dijkstra）在1956年提出的。Dijkstra算法主要特点是从起始点开始，采用贪心的思想，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

基本思路：

创建一个集合S，用于存储已经找到最短路径的顶点。
将所有顶点的最短路径估计值初始化为无穷大（或一个非常大的数），除了源点其值为0。
不断从未加入S的顶点中选择一个具有最小估计值的顶点u，加入到S中。
更新u的所有邻接顶点v的最短路径估计值。如果通过u到达v的路径比当前已知的路径更短，则更新v的估计值。
重复步骤3和4，直到所有顶点都被加入到S中。

c++代码

#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;

struct route {
    int v;  //路径通向的城市编号
    int w;  //路径承重
    int d;  //路径长度
};

int main() {
    int n, m, h, u, v, w, d;
    cin >> n >> m >> h;
    unordered_map<int, vector<route>> mp;
    int l = 1e9, r = 0;
    for (int i = 0; i < m; ++i) {
        cin >> u >> v >> w >> d;
        if (w < l) l = w;
        if (w > r) r = w;
        mp[u].push_back({v, w, d});
        mp[v].push_back({u, w, d});
    }
    int ans = -1;
    while (l <= r) {
        int mid = (l + r) / 2; //二分取中值
        //迪杰斯特拉(Dijkstra)算法，计算单源最短路径
        vector<int> dis(n + 1, h + 1);  //初始化每个点的路径长为一个大数
        vector<bool> flag(n + 1, false);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
        pq.push({dis[1] = 0, 1});
        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            if (flag[u]) continue;//剪枝，该点已经在最优集合中
            if (u == n) break;
            flag[u] = true;
            for (route& r : mp[u]) {    //更新u的所有邻接顶点
                if (r.w >= mid && d + r.d < dis[r.v]) {
                    pq.push({dis[r.v] = d + r.d, r.v});
                }
            }
        }
        if (dis[n] > h) {
            r = mid - 1;//缩小区间，找值更小的解
        } else {
            ans = mid;  //更新结果
            l = mid + 1;//缩小区间，继续二分找更大的解
        }
    }
    cout << ans;
}

题解 | 游游出游 c++ 二分答案&单源最短路径

知识点1：二分答案

知识点2：单源最短路径

c++代码