解题报告：luoguP1462 通往奥格瑞玛的道路（二分、最短路）

我们直接二分答案，二分过路费，每次Dij判断走所有小于当前mid的路能否到达终点且最短路（总扣血）小于最大血量。
先dij一下一个极大值，看看能否到达终点。
注意b是血量，而二分的是价格，不是一个东西。
血量是边权， 价格是点权，不要搞混。
数据有可能爆int，应该改成$ll$ll。

因为数据中过路费最大为1e9， $log_2(1e9)<30$log2​(1e9)<30
所以总时间复杂度为$O(30 * nlogn)$O(30∗nlogn)，而n为$1e4$1e4 ，所以稳过

#include<queue>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll, int> PII;

const int N = 500007, M = 50000007, INF = 0x3f3f3f3f;
int n, m;
ll b;
int ver[M], edge[M], nex[M], head[N], tot;
ll f[N];
ll dist[N];
bool vis[N];

void add(int x, int y, int z){
    ver[tot] = y;
    edge[tot] = z;
    nex[tot] = head[x];
    head[x] = tot ++ ;
}

bool Dijkstra(ll maxx){
    memset(dist, 0x3f, sizeof dist);
    memset(vis, 0, sizeof vis);

    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII> >q;
    q.push({0, 1});

    while(q.size()){
        int x = q.top().y;
        q.pop();
        if(vis[x])continue;
        vis[x] = true;

        for(int i = head[x]; ~i; i = nex[i]){
            int y = ver[i], z = edge[i];
            if(dist[y] > dist[x] + z && f[y] <= maxx){
                dist[y] = dist[x] + z;
                q.push({dist[y], y});
            }
        }
    }
    return dist[n] <= b;
}

int main(){
    scanf("%d%d%lld", &n, &m, &b);
    memset(head, -1, sizeof head);
    for(int i = 1;i <= n; ++ i)
        scanf("%lld", &f[i]);
    for(int i = 1;i <= m;++ i){
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        if(x == y)continue;
        add(x, y, z);
        add(y, x, z);
    }

    if(!Dijkstra(INF)){
        puts("AFK");
        return 0;
    }

    ll l = 1, r = 1e10 + 10;
    while(l < r){
        ll mid = l + r >> 1;
        if(Dijkstra(mid))r = mid;
        else l = mid + 1;
    }
    printf("%lld\n", r);
    return 0;
}