题解 P3403 【跳楼机】

觞羰涙 · 2018-12-15 17:30:40 · 题解

第一道感觉懂得不错的同余最短路题

详见代码注释

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<iomanip>
#define maxn 100005
typedef long long ll;
const int inf = 0x3f3f3f3f;
int cnt;
int head[maxn],vis[maxn];
ll dis[maxn];
ll h,x,y,z;
using namespace std;
template <class T> void read(T &x)
{
    x=0;int f=1;char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    x*=f;
}
struct fuck
{
    int to,next;
    ll w;
}e[maxn<<1];
void add(int u,int v,ll w)
{
    e[cnt].w=w;
    e[cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt++;
}
void SPFA()
{
    queue<int>q;
    memset(dis,inf,sizeof(dis));
    dis[1]=1;vis[1]=1;q.push(1);//起点在高度1
    while(!q.empty())
    {
        int u=q.front();
        vis[u]=0;q.pop();//正常最短路 
        for(int i=head[u];~i;i=e[i].next)
        {
            int j=e[i].to;
            if(dis[j]>dis[u]+e[i].w)
            {
                dis[j]=dis[u]+e[i].w;
                if(!vis[j])
                {
                    q.push(j);
                    vis[j]=1;
                }
            }
        }
    }
}
int main()
{//dis[i]表示求余y(简单情况)或z余数为i的前面数总和的最小值
//这样y(或者z)就有最多的取值情况 
    memset(head,-1,sizeof(head));
    read(h);read(x);read(y);read(z);
    if(!z)
    {//先考虑简单的情况 k1*x+k2*y=h 
        for(int i=0;i<y;i++)add(i,(i+x)%y,x);//先给到求余y的不同余数建边 
        SPFA();ll ans=0;
        for(int i=0;i<y;i++)
        if(h>=dis[i])ans+=(h-dis[i])/y+1;//z的系数可以取0~(h-dis[i])/y的不同方案 
        printf("%lld",ans);
        return 0;
    }
    if(z==1)printf("%lld",h);
    else
    {//z!=0同理 
        for(int i=0;i<z;i++)
        {
            add(i,(i+x)%z,x);
            add(i,(i+y)%z,y);
        }   SPFA(); ll ans=0;
        for(int i=0;i<z;i++)
        if(h>=dis[i])ans+=(h-dis[i])/z+1; 
        printf("%lld",ans);
    }
    return 0;
}