题意

游游准备去开车旅行，她初始在1号城市，准备前往n号城市。游游打开了携程，她查询到了地图上有若干城市，城市之间有一些道路连接。每条道路有承重限制，当游游的车重量超过了承重时，她就不能走这条道路。游游是一个贪心的人，她希望总路程不超过h的前提下，携带尽可能多的物品出行。游游想知道，自己的车最多重量能达到多少？

思路

题目求的是 车的重量的最大值

单调性：如果车的重量为10时，可以走到终点，那么车的重量为5的时候也一定可以走到终点，因为车的重量减少后，可走的道路只多不少。

所以可以二分答案，考虑下如何check

当前的重量是x的话，对于每条道路u,v,w，如果w>=x的话，这条道路才能被作为可走的道路。不用每次重新建图，只需要在跑最短路的时候，这里用的是dijkstra，如果碰到当前的边的w<x，跳过当前边即可。起点是1，如果到终点的距离<=h的话，说明这个重量可以到达，就记录答案并且移动左端点，看能不能找到更大的重量

Cpp代码

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

const int maxn = 2e6 + 10;

typedef pair<long long, long long> PII;

int n, m, maxVal;
int h[maxn], w[maxn], e[maxn], ne[maxn], idx,d[maxn];
long long dis[maxn];
bool st[maxn];

void add(int a, int b, int c,int dd) {
    e[idx] = b, w[idx] = c,d[idx] = dd, ne[idx] = h[a], h[a] = idx++;
}
bool dijkstra(int limit) {
    for (int i = 0; i <= n + 3; i++) {
        dis[i] = 1e18;
        st[i] = false;
    }
    dis[1] = 0;
    ///建立一个维护最小值的优先队列
    priority_queue<PII, vector<PII>, greater<PII>>heap;
    heap.push({0, 1}); ///起始点放入队列
    while (heap.size()) {
        auto t = heap.top(); ///最小值
        heap.pop();
        long long ver = t.second, dd = t.first;
        if (st[ver]) continue; ///该点更新
        st[ver] = true;
        for (int i = h[ver]; i != -1; i = ne[i]) {
            int j = e[i];
            if(w[i] < limit) {
                continue ;
            }
            if (dis[j] > dd + d[i]) {
                dis[j] = dd + d[i];
                heap.push({dis[j], j});
            }
        }
    }
    return dis[n] <= maxVal;
}


int main() {
    cin >> n >> m >> maxVal;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= m; i++) {
        int u, v, w,dd;
        cin >> u >> v >> w >> dd;
        add(u, v, w,dd);
        add(v,u,w,dd);
    }
    int l = 0,r = 1e9,res =-1;
    while(l<=r) {
        int mid = (l+r+1) / 2;
        if (dijkstra(mid)) {
            res = mid ;
            l = mid + 1;
        }else{
            r = mid - 1;
        }
    }
    cout<<res;






    return 0;
}