题解 P3403 【跳楼机】

FZzzz · 2020-05-25 16:35:56 · 题解

咋都是 SPFA，卡一下不就死了吗。

还有 dijkstra，咋没人写 01bfs 啊。

大概做法其他题解已经说得很清楚了，就是设 d_u 为膜 x 得 u 的能到达的最小楼层，然后跑最短路。

但是这样的话是个带权最短路。我们令 d_u 为上面那个 d_u 除以 x 向下取整，然后钦定 x\ge y,z，这样的话每次转移的边权只有可能是 0 或者 1，就可以 01bfs 了。

然后就是不要像我这种入门选手一样不会写 01bfs……

#include<queue>
#include<cctype>
#include<cstdio>
using namespace std;
typedef long long ll;
inline ll readint(){
    ll x=0;
    bool f=0;
    char c=getchar();
    while(!isdigit(c)&&c!='-') c=getchar();
    if(c=='-'){
        f=1;
        c=getchar();
    }
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return f?-x:x;
}
const int maxx=1e5+5;
int x,y,z;
ll h;
const int inf=2e9;
int d[maxx],p[maxx];
bool vis[maxx];
void bfs(){
    for(int i=0;i<x;i++) d[i]=inf;
    deque<int> q;
    d[1]=0;
    q.push_back(1);
    while(!q.empty()){
        int u=q.front();
        q.pop_front();
        if(vis[u]) continue;
        vis[u]=1;
        if(u+y<x){
            if(d[u+y]>d[u]){
                d[u+y]=d[u];
                q.push_front(u+y);
            }
        }
        else{
            if(d[u+y-x]>d[u]+1){
                d[u+y-x]=d[u]+1;
                q.push_back(u+y-x);
            }
        }
        if(u+z<x){
            if(d[u+z]>d[u]){
                d[u+z]=d[u];
                q.push_front(u+z);
            }
        }
        else{
            if(d[u+z-x]>d[u]+1){
                d[u+z-x]=d[u]+1;
                q.push_back(u+z-x);
            }
        }
    }
}
int main(){
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    h=readint();
    x=readint();
    y=readint();
    z=readint();
    if(x<y) swap(x,y);
    if(x<z) swap(x,z);
    if(x==1){
        printf("%lld\n",h);
        return 0;
    }
    bfs();
    ll ans=0;
    for(int i=1;i<x;i++) if(vis[i]&&h/x+(h%x>=i)>=d[i])
        ans+=h/x+(h%x>=i)-d[i];
    if(vis[0]&&h/x-d[0]+1>=0) ans+=h/x-d[0]+1;
    printf("%lld\n",ans);
    return 0;
}