题目：
松鼠宝宝由于贪玩去了一个具有n个点和m条边的无向图中，现在松鼠宝宝仅有h点体力，所有的边经过一次后会消耗部分体力，同时松鼠爸爸为了惩罚贪玩的松鼠宝宝，每到一个点会扣除部分松果（起点的松果也会扣除）。现松鼠宝宝向你求助，询问在能到达家的情况下尽可能让路径上扣除松果的数量最大的那个点扣除的数量尽可能小。

**最大值最小  所以用二分**  
二分的是扣除的松果的数量，用dijkstra来求路径

memset是通过字节来赋值的，0x3f是对int类型的最大值赋值，开了longlong之后就不可以用它了，但是也不可以用除了0，-1，false等特殊值之外的普通常量来进行赋值

找消耗最小体力的路径

//在扣除x个松果的情况下进行dijkstra
int dijkstra(int x)
{
    //初始化
    memset(st, false, sizeof st);
    //这里不能通过memset来赋值， 
    for(int i = 1; i <= n; i ++) dist[i] = 1e18; 
    dist[start] = 0;

    //小根堆，按照first从小到大进行排序
    priority_queue<PII, vector<PII>, greater<PII>>q;


    q.push({0, start});   //first 是消耗的体力， second是点
    if(a[start] > x) return 1e18; //如果起点所扣除的松果数量就已经大于x了，就返回无穷大


    while(q.size())
    {
        auto t = q.top();
        q.pop();
        int fir = t.first, sec = t.second;


        if(st[sec]) continue; //如果已经走过这个点，就跳过，否则继续，且标记一下
        st[sec] = true;

        for(int i = h[sec]; i != -1; i = ne[i])
        {
            int j = e[i];


            if(a[j] > x) continue; //如果该点扣除的松果数量大于x，就跳过

            if(dist[j] > w[i] + dist[sec]) //找消耗体力最小的路径
            {
                dist[j] = w[i] + dist[sec];
                q.push({dist[j], j});
            }

        }
    }
    return dist[ed];
}

二分找最大值的最小

bool check(int x)//验证, 如果在扣除x个松果的情况下消耗的体力大于已给的体力的话，该情况不成立
{
    if(dijkstra(x) > hh) return false;
    return true;
}

//如果无法回家，输出-1
    if(!check(1e18))
    {
        cout << "-1" << endl;
        return 0;
    }

    int l = 1, r = 2e7;//二分找最大值的最小
    while(l < r)
    {
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }

    cout << l << endl;

源代码

#include <queue>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

typedef pair<int, int>PII;
#define int long long

const int N = 1e5;
int e[N], h[N], ne[N], w[N], idx;
int start, ed, n, m, hh;
int a[N];                 //每个点扣除的松果数量
int dist[N];              //消耗的体力
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a];
    w[idx] = c, h[a] = idx ++;
}

int dijkstra(int x)
{
    memset(st, false, sizeof st);
    for(int i = 1; i <= n; i ++) dist[i] = 1e18;
    dist[start] = 0;

    priority_queue<PII, vector<PII>, greater<PII>>q;
    q.push({0, start});

    if(a[start] > x) return 1e18;

    while(q.size())
    {
        auto t = q.top();
        q.pop();
        int fir = t.first, sec = t.second;

        if(st[sec]) continue;
        st[sec] = true;

        for(int i = h[sec]; i != -1; i = ne[i])
        {
            int j = e[i];

            if(a[j] > x) continue;

            if(dist[j] > dist[sec] + w[i])
            {
                dist[j] = dist[sec] + w[i];
                q.push({dist[j], j});
            }
        }
    }
    return dist[ed];
}

bool check(int x)
{
    if(dijkstra(x) > hh) return false;
    return true;
}

signed main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m >> start >> ed >> hh;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    while(m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }

    if(!check(1e8))
    {
        cout << "-1" << endl;
        return 0;
    }

    int l = 1, r = 2e7;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
    return 0;
}