题解 P1462 【通往奥格瑞玛的道路】

题解-P1462 通往奥格瑞玛的道路

$1.1$ 题目意思

题目意思很简单，就是你要从 $1$ 到 $n$ ，你有 $b$ 的血量，每次从一个城市到另一个城市会消耗 $bi$ 的血量，每个城市需要花 $wi$ 的费用。现在问你当你的 $0\leq b$ 时，他所经过的所有城市中最多的一次收取的费用的最小值是多少。

$2.1$ 算法思路

题目要求我们求最小值显然想到用二分求解呀。我们直接二分答案。但是需要注意的是：当你二分完后，但不一定而分出了答案，所以要对答案进一不验证，就是判断当你血量还是大于 $0$ 时是否达到了城市 $n$ 。在 $check$ 的时候，对于 $mid\leq f[n]$ 或者 $mid\leq f[1]$ ，直接 $continue$ 掉，然后对于 $mid\leq f[i]$ 的 $vis[i]=1$ 即可。

$3.1$ 代码实现

#include <bits/stdc++.h>
#define re register
#define int long long 
using namespace std;

const int maxn=1e5+5,maxm=5e5+5;
struct nood {
    int nex,to,w;
} e[maxm];
int head[maxn],dis[maxn],vis[maxn];
int n,m,b,cnt,ans,now,maxf,f[maxn],ff=0;

inline void add_edge(int u,int v,int len) {
    e[++cnt].nex=head[u];
    head[u]=cnt;
    e[cnt].to=v;
    e[cnt].w=len;
}
//前向星连边
inline int read() {
    int sum=0; char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) sum=sum*10+ch-'0',ch=getchar();
    return sum;
}
//快读
inline bool spfa(int x) {
    queue<int>ma;
    memset(vis,0,sizeof(vis));
    memset(dis,0x7f,sizeof(dis));
    ma.push(1),dis[1]=0,vis[1]=1;
    for ( re int i=1;i<=n;i++ ) 
        if(f[i]>x) vis[i]=1;
    //对于那些mid<f[i]的点标记为1
    while(!ma.empty()) {
        int u=ma.front(); 
        ma.pop(); 
        vis[u]=0;
        for ( re int i=head[u];i;i=e[i].nex ) {
            int v=e[i].to;
            if(dis[v]>dis[u]+e[i].w) {
                dis[v]=dis[u]+e[i].w;
                if(!vis[v]) {
                    vis[v]=1;
                    ma.push(v);
                }
            }
        }
    }//普通的最短路spfa
    if(dis[n]>b) return false;
    ff=1;
    return true;
    while(ma.size()) ma.pop();
}

signed main() {
    n=read(),m=read(),b=read();
    for ( re int i=1;i<=n;i++ ) 
        f[i]=read();
    for ( re int i=1;i<=m;i++ ) {
        int u=read(),v=read(),z=read();
        add_edge(u,v,z);
        add_edge(v,u,z);
    }
    int l=0,r=1e10;
    while(l<=r) {
        int mid=(l+r)/2;
        if(mid<f[n]||mid<f[1]) {
            l=mid+1;
            continue;
        }
        //对于而二分出的值小于f[1]或者f[n]直接跳过，并且l++，不l++会进入死循环。
        if(spfa(mid)) r=mid-1,ans=mid;
        else l=mid+1;
    }
    if(ff==0 && !spfa(ans)) 
        return printf("AFK\n"),0;
    //如果ff到达标记还是0，并且当前答案还是不对，输出AFK
    printf("%lld\n",ans);
    return 0;
}

$4.1$ 总结

这道题目其实很简单，就是二分+ $spfa$ ，仔细想一想肯定能够 $AC$ 的。