P1462 通往奥格瑞玛的道路

二分最大点权，最短路检查边权和

问题

P1462 通往奥格瑞玛的道路
无向图中每座城市收取一次费用，每条道路会造成一定血量损失。角色从城市 $1$ 前往城市 $n$，路径总损血不能超过血量上限 $b$；在所有可行路径中，要求路径经过城市的单次收费最大值尽量小，无解输出 AFK。

数据规模：$1\le n\le10^4$，$1\le m\le5\times10^4$，$1\le b,c_i\le10^9$，$0\le f_i\le10^9$，可能存在重边。

本题有两个优化目标，一个是路径和要求小于等于 $b$，一个是路径经过城市的点权最大值尽可能小。

前者我们只需要算出两点最短路即可，后者我们可以想到二分答案，二分允许经过的最大收费 $mid$。

于是做法显然：暂时删去所有收费大于 $mid$ 的城市，再用 Dijkstra 求剩余图中从 $1$ 到 $n$ 的最小损血量，判断它是否不超过 $b$。

接着证明单调性，随着 $mid$ 增大，可以选择的城市只会越来越多，可行性是单调的，于是我们二分寻找第一个可行的答案。

答案一定来自某座城市的收费，二分边界可取 $\max(a_1,a_n)$ 到 $\max a_i$。复杂度为 $O((n+m)\log n\log V)$，其中 $V$ 是收费值域。

▶

P1462

struct Edge { int v; ll w; };
vector<Edge> adj[maxn];

struct State {
    int u; ll d; // health
    bool operator < ( const State &oth ) const { return d > oth.d; }
};

ll dis[maxn];
ll a[maxn];
ll b;

bool dijkstra( int S, int N, ll mid ) {
    if( a[S] > mid || a[N] > mid ) return 0;
    fill( dis + 1, dis + N + 1, inf );
    priority_queue<State> pq;
    dis[S] = 0, pq.push({ S, 0 });
    while( !pq.empty( ) ) {
        auto [u, d] = pq.top( ); pq.pop( );
        if( d > b ) continue;
        if( d > dis[u] ) continue;
        for( auto [v, w] : adj[u] ) {
            if( a[v] > mid ) continue;
            if( d + w < dis[v] ) {
                dis[v] = d + w;
                pq.push({ v, dis[v] });
            }
        }
    }
    return dis[N] <= b;
}

void solve( ) {
    int n = read( ), m = read( ); 
    b = read( );

    ll mx = 0;
    for( int i = 1; i <= n; ++ i ) {
        a[i] = read( );
        mx = max( mx, a[i] );
    }

    for( int i = 1; i <= m; ++ i ) {
        int u = read( ), v = read( );
        ll w = read( );
        adj[u].push_back({ v, w });
        adj[v].push_back({ u, w });
    }

    ll l = max( a[1], a[n] ), r = mx, ans = -1;
    while( l <= r ) {
        ll mid = ( l + r ) >> 1;
        if( dijkstra( 1, n, mid ) ) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    if( ans == -1 ) cout << "AFK" << '\n';
    else cout << ans << '\n';
}