Luogu P1462 通往奥格瑞玛的道路

搜索

提供一种不一样的做法。

我在写这个题的时候刚刚学了二分和搜索 还不会最短路，就把这个题当做二分题写了。可能是数据比较水吧。首先看到最小值最大或者最大值最小，我们的第一直觉就是二分答案。

我们二分最大值，我们只走那些小于等于二分的答案的路，如果我们能够走到终点，就说明我们设置的条件比较弱，我们就可以减小二分的答案，当我们走不到终点的时候，就说明我们二分的条件比较严，我们就应该调大我们二分的答案，一直这样下去我们就能找到一个比较精确的值，当这个条件精确到唯一的一个值的时候，我们就二分到了我们要的答案。

二分答案很重要的就是check()函数了，很多大佬都是写的最短路（dijkstral/spfa），将掉血量看成路的长度，看看符合条件的掉血量是否符合条件，然后再调整mid值，继续二分。二分的复杂度为\(O(log(n))\),然后再乘上最短路的时间复杂度，就是整体的时间复杂度。但是我写这个题的时候还不会写最短路，之好写了搜索，但可能是数据比较水，被我水过了，当然，我后续会补上关于最短路的题解。

以下就是我的早期代码，可能存在的问题比较多，倘若有什么问题，还望大家不吝赐教，指出我的错误。

最后献上我丑陋的代码

#include<iostream>
#include<cstdio>
using namespace std;
struct bian
{
    int to,nt,dis;
}e[100001];
int f[10001],head[10001],tot,ans;
bool flag=0;
int n,m,b,x,y,z;
void add(int from,int to,int dis)
{
    e[++tot].to=to;
    e[tot].dis=dis;
    e[tot].nt=head[from];
    head[from]=tot;
}
void check(int fr,int l,int x,int q)
{   
    if(f[1]>q||f[n]>q) {flag=0;return;}
    if(fr==n)          {flag=1;return;}
    for(int i=head[fr];i;i=e[i].nt)
    {
        if(f[e[i].to]<=q&&x-e[i].dis>0&&e[i].to!=l)
        {
            check(e[i].to,fr,x-e[i].dis,q); 
        }
        if(flag==1)return;
    }
}
int main()
{
    cin>>n>>m>>b;
    for(int i=1;i<=n;++i)scanf("%d",&f[i]);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);add(y,x,z);
    }
    int l=0,r=2147483646;
    check(1,0,b,2147483646);
    if(flag==0)
    {
        cout<<"AFK";
        return 0;
    }
    while(l<=r)
    {
        flag=0;
        int mid=(l+r)>>1;
        check(1,0,b,mid);
        if(flag==1)
        {
            r=mid-1;
            ans=mid;
        }
        else l=mid+1;
    }
    cout<<ans;
    return 0;
}

update

已经补上关于最短路的题解(SPFA)

#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
using namespace std;
const int N=10010;
struct bian
{
    int to,nt,dis;
}e[100001];
int n,m,b,x,y,z,tot,ans;
int f[N],head[N];
long long dis[N];
bool vis[N];
void add(int from,int to,int dis)
{
    e[++tot].to=to;
    e[tot].dis=dis;
    e[tot].nt=head[from];
    head[from]=tot;
}
bool check(int mid)
{   
    if(f[1]>mid||f[n]>mid)return 0;
    memset(dis,0x3f,sizeof(dis));
    queue<int>q;
    q.push(1);
    vis[1]=1;dis[1]=0;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();vis[x]=0;
        for(int i=head[x];i;i=e[i].nt)
        {
            if(f[e[i].to]>mid)continue;
            if(dis[e[i].to]>dis[x]+e[i].dis)
            {
                dis[e[i].to]=dis[x]+e[i].dis;
                if(!vis[e[i].to])
                {
                    q.push(e[i].to);
                    vis[e[i].to]=1;
                }
            }
        }
    }
    return dis[n]<b;
}
int main()
{
    cin>>n>>m>>b;
    for(int i=1;i<=n;++i)scanf("%d",&f[i]);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);add(y,x,z);
    }
    int l=0,r=2147483646;
    if(!check(2147483646))
    {
        cout<<"AFK";
        return 0;
    }
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check(mid))
        {
            r=mid-1;
            ans=mid;
        }
        else l=mid+1;
    }
    cout<<ans;
    return 0;
}

效率高了一倍,珍爱生命，远离 乱搞