poj 3539 Elevator

题面

解题思路

同余类bfs 。构造a个点，为什么只要a个呢？是因为如果能到达某个0~a-1的点x，那么x+a，x+2*a ….等都可以到达。然后我们考虑从x出发，可以到达x+b与x+c，所以我们将x与x+b，x+c分别相连，权值分别为b,c，然后跑一次最短路，得到的dis[x]一定是最早能到达的点，然后dis[x]+a,dis[x]+2* a也都一定可以到达，并且也用上了b，c所能做的共献。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define LL long long

using namespace std;
const int MAXN = 200005;
const int inf = 0x3f3f3f3f;

LL ans,h;
LL a,b,c,dis[MAXN];
int head[MAXN],cnt;
int to[MAXN<<1],nxt[MAXN<<1],val[MAXN<<1];
bool vis[MAXN];
queue<int> q;

inline void add(int bg,int ed,int v){
    to[++cnt]=ed,nxt[cnt]=head[bg],head[bg]=cnt,val[cnt]=v;
}

inline void spfa(){
    memset(dis,0x3f,sizeof(dis));
    q.push(1%a);vis[1%a]=1;dis[1%a]=1;
    while(q.size()){
        int x=q.front();q.pop();
        vis[x]=0;
        for(register int i=head[x];i;i=nxt[i]){
            int u=to[i];
            if(dis[u]>dis[x]+val[i]){
                dis[u]=dis[x]+val[i];
                if(!vis[u]){
                    q.push(u);
                    vis[u]=1;
                }
            }
        }
    }
}

int main(){
    cin>>h>>a>>b>>c;
    if(a>b) swap(a,b);
    if(a>c) swap(a,c);
    for(register int i=0;i<a;i++){
        add(i,(i+b)%a,b);
        add(i,(i+c)%a,c);
    }spfa();
//  for(register int i=0;i<a;i++) cout<<dis[i]<<" ";
    for(register int i=0;i<a;i++)if(dis[i]<=h)
        ans+=(h-dis[i])/a+1;
    cout<<ans;
    return 0;
}