跳楼机
跳楼机
题目描述
Srwudi的家是一幢h层的摩天大楼。由于前来学习的蒟蒻越来越多，srwudi改造了一个跳楼机，使得访客可以更方便的上楼。
经过改造，srwudi的跳楼机可以采用以下四种方式移动：
1、向上移动x层；
2、向上移动y层；
3、向上移动z层；
4、回到第一层。
一个月黑风高的大中午，DJL来到了srwudi的家，现在他在srwudi家的第一层，碰巧跳楼机也在第一层。
DJL想知道，他可以乘坐跳楼机前往的楼层数。
输入格式
第一行一个整数h，表示摩天大楼的层数。
第二行三个正整数，分别表示题目中的x, y, z。
输出格式
一行一个整数，表示DJL可以到达的楼层数。
样例数据
input
15
4 7 9
output
9
样例解释
可以到达的楼层有：1,5,8,9,10,12,13,14,15
数据规模与约定
对于20%的数据，1≤h, x, y, z≤100；
对于40%的数据，1≤h, x, y, z≤10^5；
对于100%的数据，1≤h≤10^18，1≤x, y, z≤10^5。
时间限制：1s
空间限制：256MB
这题有一点偏数学……
需要用到最短路模型，主要还是思维难度~
代码很简单的
#include<bits/stdc++.h>
using namespace std;
long long h,x,y,z,ans,len;
const int N=100005;
long long last[N*2],f[N*2],dis[N*2];
bool vis[N*2];
struct ss
{
int to,next,v;
}e[N*2];
void insert(long long x,long long y,long long v)
{
e[++len].next=last[x];
e[len].to=y;
e[len].v=v;
last[x]=len;
}
queue<long long> q;
void SPFA()
{
memset(f,0x3f3f3f,sizeof(f));
f[1]=1,vis[1]=1;
q.push(1);
while(!q.empty())
{
long long _x=q.front(),i=last[_x];
for(q.pop();i;i=e[i].next)
{
long long v=e[i].to;
if(f[v]>f[_x]+e[i].v)
{
f[v]=f[_x]+e[i].v;
if(!vis[v])vis[v]=1,q.push(v);
}
}
vis[_x]=0;
}
}
int main()
{
freopen("srwudi.in","r",stdin);
freopen("srwudi.out","w",stdout);
int i=-1;
scanf("%lld%lld%lld%lld",&h,&x,&y,&z);
if(x==1||y==1||z==1)
{
printf("%lld",h);
return 0;
}
if(x>y)swap(x,y);if(y>z)swap(y,z);if(x>z)swap(x,z);
for(i=-1;++i<=x-1;)
{
insert(i,(i+y)%x,y);
insert(i,(i+z)%x,z);
}
SPFA();
for(i=-1;++i<=x-1;)
if(h>=f[i])ans+=(h-f[i])/x+1;
printf("%lld",ans);
return 0;
}
谢谢观赏哦~~
相关阅读
初见安~这里是传送门：洛谷P1991 题目描述 国防部计划用无线网络连接若干个边防哨所。2 种不同的通讯技术用来搭建无线网络； 每个边