【题解】跳楼机 同余最短路 luogu3403

说实话，这道题主要还是思维。

对于 $x,y,z$ 三个操作，我们先考虑 $y,z$ 两个操作的情况。

$f[i]$ 表示通过 $y,z$ 两个操作可以到达的 $mod x=i$ 最小的楼层。

可以得知：$f[i+y]=f[i]+y,f[i+z]=f[i]+z.$

对于最短路，我们可以用一下形式建边：

   add(i,(i+y)%x,y); add(i,(i+z)%x,z);

没问题吧？%x 是必须要做的操作，上文讲了。

那如何统计答案呢？

首先，如果这个 “ 最小的楼层” 超出了 $H$ ，那么显然是不用统计的。否则，我们将这样统计：ans+=(H-f[i])/x+1;

为什么要这样写呢？想想，现在我们知道了这个最小楼层，我们可以到达这个最小楼层，对吧？如果现在以这个最小楼层为起点，我们可以选择在往上跳 $x$ 层，或者是 $2x$ 层…. 知道 $nx$ 层，$(n+1)x$就会超出 $H$，这时上面的式子就好理解多了。

Code:(可以不用 堆优 $Dijstra$，没必要，用 $Spfa$ 就行了)

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define RI register int
using namespace std;
const int N=1e5+3;
ll H,x,y,z,ans,f[N];
int vis[N],head[N],cnt;
struct Edge{int nxt,to,val;}G[N<<1]; 
inline void add(int x,int y,int v)
{G[++cnt].nxt=head[x],G[cnt].to=y,G[cnt].val=v,head[x]=cnt;}
inline void spfa(){
    memset(f,127,sizeof(f));
    queue<int> q;f[1]=1,vis[1]=1,q.push(1);
    while(q.size()){
        int x=q.front();q.pop();vis[x]=0;
        for(RI i=head[x];i;i=G[i].nxt){
            if(f[G[i].to]>f[x]+G[i].val){
                f[G[i].to]=f[x]+G[i].val;
                if(!vis[G[i].to])q.push(G[i].to),vis[G[i].to]=1;    
            }
        } 
    }return;
}
int main(){
    scanf("%lld%lld%lld%lld",&H,&x,&y,&z);
    if(x==1||y==1||z==1){printf("%lld\n",H);return 0;}
    for(int i=0;i<x;++i){add(i,(i+y)%x,y);add(i,(i+z)%x,z);} 
    spfa();
    for(int i=0;i<x;++i)
       if(f[i]<=H)ans+=(H-f[i])/x+1;
    printf("%lld\n",ans); 
    return 0;
}