【洛谷P1462】通往奥格瑞玛的道路

题目大意：给定一个 N 个点，M 条边的无向图，求从 1 号节点到 N 号节点的路径中，满足路径长度不大于 B 的情况下，经过顶点的点权的最大值最小是多少。

题解：最大值最小问题一般采用二分答案。这道题二分经过的点权，每次用二分出来的值跑最短路，在 dij 的过程中保证扩展的节点都是点权小于 mid 的即可，最后比较到 N 号节点的最短路长度是否小于给定的 B 即可。

代码如下

#include <bits/stdc++.h>

using namespace std;

const int maxn=1e4+10;

const int maxe=1e5+10;

const long long inf=1e18;

inline int read(){

    int x=0,f=1;char ch;

    do{ch=getchar();if(ch=='-')f=-1;}while(!isdigit(ch));

    do{x=x*10+ch-'0';ch=getchar();}while(isdigit(ch));

    return f*x;

}

struct node{

    int nxt,to;

    long long w;

}e[maxe<<1];

int tot=1,head[maxn];

inline void add_edge(int from,int to,long long w){

    e[++tot]=node{head[from],to,w},head[from]=tot;

}

int n,m;

long long val[maxn],d[maxn],bld,mx;

bool vis[maxn];

void read_and_parse(){

    n=read(),m=read(),bld=read();

    for(int i=1;i<=n;i++)val[i]=read(),mx=max(mx,val[i]);

    for(int i=1,x,y,z;i<=m;i++){

        x=read(),y=read(),z=read();

        add_edge(x,y,z),add_edge(y,x,z);

    }

}

typedef pair<int,int> P;

#define mp make_pair

priority_queue<P> q;

bool right(int mid){

    if(val[1]>mid)return 0;

    fill(d+1,d+n+1,inf),fill(vis+1,vis+n+1,0);

    d[1]=0,q.push(mp(0,1));

    while(q.size()){

        int u=q.top().second;q.pop();

        if(vis[u])continue;

        vis[u]=1;

        for(int i=head[u];i;i=e[i].nxt){

            int v=e[i].to;long long w=e[i].w;

            if(val[v]<=mid&&d[u]+w<d[v])d[v]=d[u]+w,q.push(mp(-d[v],v));

        }

    }

    return d[n]<=bld;

}

void solve(){

    int l=0,r=mx+1;

    bool flag=0;

    while(l<r){

        int mid=l+r>>1;

        if(right(mid))r=mid,flag=1;

        else l=mid+1;

    }

    if(!flag)puts("AFK");

    else printf("%d\n",r);

}

int main(){

    read_and_parse();

    solve();

    return 0;

}