P3403 跳楼机

· · 题解

偶然间发现了去年做过的这题那就写一下题解叭qwq.

知识点：最短路

思路：操作1-4分别为：回到1；上升a层；上升b层；上升c层；

用f[i]（我的理解就是楼层间隔）存仅通过第3，4种方式移动所能到达的mod a= i的最小楼层。

举个栗子：
当前a=4,b=2,c=3时；
此时所能到达的最小楼层为6；
则 6 mod 4 = 2；所以 f[2] = 6。

理解了上面的步骤就可以得出仅通过3操作或4操作求出f[i]的式子。

3操作：f[i+b] = f[i] + b;
//能到达mod a=i+b的最小楼层即在能到达mod a=i的最小楼层的基础上再执行一遍3操作，4操作同理；
4操作: f[i+c] = f[i] + c。

从这里我们可以看出与最短路的模板相似：

dist[x] = dist[y] + z。

接下来统计答案:

因为f[i]只是通过3操作与4操作所能到达的mod a= i的最小楼层，所以我们还可以通过2操作到达更高的楼层，那么在统计答案时就很简单了，即；

ans +=（h-d[i]）/ a + 1；
"+1" 是它本身的楼层。

做完以上步骤即可。

（题外话：因为忘记STL大根堆是按第一个关键字排序的憨憨调了一个小时。。。话说spfa好像更快但是它还是死了）

CODE：

#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=1e5+100;
long long n,a,b,c,ans,tot;
long long d[N],ver[N<<1],head[N],edge[N<<1],Next[N<<1];
bool v[N];
priority_queue< pair<long long,long long> > q;

inline void add(int x,int y,int z){
    ver[++tot]=y,edge[tot]=z,Next[tot]=head[x],head[x]=tot;
}

inline void dijkstra(){
    memset(d,0x3f3f,sizeof(d));
   //long long下的最大值是0x3f3f3f3f3f3f3f3f然后memset是4位4位赋值的所以就是0x3f3f
    memset(v,false,sizeof(v));
    d[1]=1;//与平常的最短路不同，因为到它本身楼层也有一次所以赋为1
    q.push(make_pair(-1,1));
    while(q.size()){
        int x=q.top().second;
        q.pop();
        if(v[x]) continue;
        v[x]=true;
        for(int i=head[x];i;i=Next[i]){
            int y=ver[i],z=edge[i];
            if(d[y]>d[x]+z){
                d[y]=d[x]+z;
                q.push(make_pair(-d[y],y));
            }
        }
    }
}

int main(){
    scanf("%lld%lld%lld%lld",&n,&a,&b,&c);
    if(a==1 || b==1 || c==1){
        printf("%lld",n);//如果有存在一种操作为上升1层显然都可到达
        return 0;
    }
    for(int i=0;i<a;i++) add(i,(i+b)%a,b),add(i,(i+c)%a,c);//建图
    dijkstra();
    for(int i=0;i<a;i++)
        if(d[i]<=n) ans+=(n-d[i])/a+1;//统计答案
    printf("%lld",ans);
    return 0;
}