LG-1462

在艾泽拉斯，有 $n$ 个城市。编号为 $1,2,3,\ldots,n$。

城市之间有 $m$ 条双向的公路，连接着两个城市，从某个城市到另一个城市，会遭到联盟的攻击，进而损失一定的血量。

每次经过一个城市，都会被收取一定的过路费（包括起点和终点）。路上并没有收费站。

假设 $1$ 为暴风城，$n$ 为奥格瑞玛，而他的血量最多为 $b$，出发时他的血量是满的。如果他的血量降低至负数，则他就无法到达奥格瑞玛。

歪嘴哦不希望花很多钱，他想知道，在可以到达奥格瑞玛的情况下，他所经过的所有城市中最多的一次收取的费用的最小值是多少。

思路

本题有点权有边权。

看到最小的最大值，秒想到二分答案。

于是直接对点权二分答案，每次跑 SPFA 判断答案可行性即可。

注意判断答案可行性时也要注意起点的点权。

代码

#include<bits/stdc++.h>
#define N 50010

using namespace std;

inline int read() {
    int w=1,x=0;
    char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return w*x;
}

int n,m,b,f[N];
vector<int> val;
bool flag=false;

int head[N],tot=0;
struct graph{
    int v,w,next;
}edge[N<<1];
void add_edge(int u,int v,int w) {
    edge[++tot].v=v;
    edge[tot].w=w;
    edge[tot].next=head[u];
    head[u]=tot;
}
void add(int u,int v,int w) {add_edge(u,v,w),add_edge(v,u,w);}

int dis[N],maxn[N];
bool vh[N];
queue<int> q;
bool SPFA(int s,int mcst) {
    memset(vh,0,sizeof(vh));
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    q.push(s);
    vh[s]=true;
    if(f[s]>mcst) return false;
    while(!q.empty()) {
        int u=q.front();q.pop();
        vh[u]=false;
        for(int i=head[u];i;i=edge[i].next) {
            int v=edge[i].v,w=edge[i].w;
            if(f[v]>mcst) continue;
            if(dis[u]<dis[v]-w) {
                dis[v]=dis[u]+w;
                if(!vh[v]) {
                    q.push(v);
                    vh[v]=true;
                }
            }
        }
    }
    if(dis[n]>b) return false;
    return true;
}

int main() {
    n=read(),m=read(),b=read();
    for(int i=1;i<=n;i++) f[i]=read();
    for(int i=1;i<=m;i++) {
        int u=read(),v=read(),w=read();
        add(u,v,w);
    }
    
    for(int i=1;i<=n;i++) val.push_back(f[i]);
    sort(val.begin(),val.end());
    int l=0,r=n;
    while(l<r) {
        int mid=l+r>>1;
        if(SPFA(1,val[mid])) {
            r=mid;
            flag=true;
        }
        else l=mid+1;
    }

    if(flag) printf("%d\n",val[l]);
    else printf("AFK\n");
    system("pause");
    return 0;
}