P1462 通往奥格瑞玛的道路·最短路+二分

题解：

大致题意，求能到达目的地的路径里单个城市花费的最大值最小的情况

最大花费最小值 → 二分，用来判断答案存在的可能性（前提条件，答案单调）

最短路用来判断能否走到目的地（问题是为啥是最短路？？）

---

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=1e6+10;
const int mx=1e9+5;
int f[N];
int n,m,b;
struct edge{
    int to,next,len;
}e[N];
int tot,head[N];
void add(int u,int v,int c){
    e[++tot].to=v;
    e[tot].len=c;
    e[tot].next=head[u];//从0开始
    head[u]=tot;
}
int dis[N],vis[N];

priority_queue< pii,vector< pii >,greater< pii > >q;

bool judge(int x){ //dijkstra 判断最高花费为x的路径是否可以走
    if(x<f[1])return 0;//如果起点都走不了
    for (int i = 1; i <= n; i++) {
        dis[i]=1e9;
    }
    memset(vis, 0, sizeof vis);
    dis[1]=0;
    q.push(make_pair(0,1));//费用 起点
    
    while(!q.empty()){
        int u=q.top().second;
        q.pop();
        if(vis[u])continue;

        vis[u]=1;

        for (int i = head[u]; i ; i = e[i].next) {//只有费用小于x的路径才能使用
            int v=e[i].to;
            int c=e[i].len;
            if(f[v] <=x && !vis[v] && dis[u]+c < dis[v]){
                dis[v]=dis[u]+c;
                q.push({dis[v],v});
            }
        }
    }

    if(dis[n]<b)return 1;
    return 0;
}
int main()
{
    scanf("%d%d%d",&n,&m,&b);
    for (int i = 1; i <= n; i++) {
        scanf("%d",&f[i]);
    }
    for (int i = 1,u,v,c; i <= m; i++) {
        scanf("%d%d%d",&u,&v,&c);
        add(u,v,c);
        add(v,u,c);
    }
    if(!judge(mx)){//如果最大可能都不能满足
        puts("AFK");
        return 0;
    }

    //二分最大收费的最小值
    int l=1,r=mx,mid;
    while(l<=r){
        mid=(l+r)>>1;
        if(judge(mid)){
            r=mid-1;
        }else l=mid+1;
    }
    printf("%d\n", l);
    return 0;
}