LuoguP3403 跳楼机-同余最短路

题目背景

DJL为了避免成为一只咸鱼,来找srwudi学习压代码的技巧。

题目描述

Srwudi的家是一幢h层的摩天大楼。由于前来学习的蒟蒻越来越多,srwudi改造了一个跳楼机,使得访客可以更方便的上楼。

经过改造,srwudi的跳楼机可以采用以下四种方式移动:

  1. 向上移动x层;
  2. 向上移动y层;
  3. 向上移动z层;
  4. 回到第一层。

一个月黑风高的大中午,DJL来到了srwudi的家,现在他在srwudi家的第一层,碰巧跳楼机也在第一层。DJL想知道,他可以乘坐跳楼机前往的楼层数。

Luogu P3403

Solution

这其实是一道同余最短路的裸题我居然没看出来???

那么问题就被转化为了求用操作2和操作3凑出$(h$ $mod$ $x$) 的最小代价,因为只要找到了这一最小代价就可以通过复用操作1来获得所有可达的楼层数,然后只需统计操作1的次数即可(所有小于h的dis[i]就是其余两种操作可以到达的楼层数,因此不会遗漏)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long LL;

const int maxn=100000+5;

template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}

int head[maxn],cnt;
LL dis[maxn];
LL h,x,y,z,ans;
bool vis[maxn];
struct edge{
int to;
int w;
int next;
}e[maxn*2];

priority_queue < pair<int,int> > q;

void add_edge(int u,int v,int w){
cnt++;
e[cnt].to=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt;
}

void dijkstra(){
memset(dis,0x3f,sizeof(dis));
dis[1]=1;
vis[1]=true;
q.push(mp(1,1));
while(!q.empty()){
int x=q.top().y;
q.pop();
vis[x]=false;
for(int i=head[x];i;i=e[i].next){
int y=e[i].to;
if(dis[y]>dis[x]+e[i].w){
dis[y]=dis[x]+e[i].w;
q.push(mp(-dis[y],y));
vis[y]=true;
}
}
}
}

/*void spfa(){
memset(dis,0x3f,sizeof(dis));
queue <int> q;
q.push(1);
vis[1]=true;
dis[1]=1;
while(!q.empty()){
int x=q.front();
q.pop();
vis[x]=false;
for(int i=head[x];i;i=e[i].next){
int y=e[i].to;
if(dis[y]>dis[x]+e[i].w){
dis[y]=dis[x]+e[i].w;
if(!vis[y]){
q.push(y);
vis[y]=true;
}
}
}
}
}*/

int main(){
h=read<LL>();
x=read<LL>();
y=read<LL>();
z=read<LL>();
if(x==1 || y==1 || z==1){//特判
printf("%lld\n",h);
return 0;
}
for(int i=0;i<x;i++){
add_edge(i,(i+y)%x,y);
add_edge(i,(i+z)%x,z);
}
dijkstra();
for(int i=0;i<x;i++){
if(dis[i]<=h){
ans+=(h-dis[i])/x+1;//除法运算是向下取整的,因此需要+1
}
}
printf("%lld\n",ans);
return 0;
}