題目背景
DJL 為了避免成為一只咸魚，來找 srwudi 學習壓代碼的技巧。
題目描述
Srwudi 的家是一幢?h?層的摩天大樓。由于前來學習的蒟蒻越來越多，srwudi 改造了一個跳樓機，使得訪客可以更方便的上樓。
經過改造，srwudi 的跳樓機可以采用以下四種方式移動：
- 向上移動?x?層；
- 向上移動?y?層；
- 向上移動?z?層；
- 回到第一層。
一個月黑風高的大中午，DJL 來到了 srwudi 的家，現在他在 srwudi 家的第一層，碰巧跳樓機也在第一層。DJL 想知道，他可以乘坐跳樓機前往的樓層數。
輸入格式
第一行一個整數?h，表示摩天大樓的層數。
第二行三個正整數，分別表示題目中的?x,y,z。
輸出格式
一行一個整數，表示 DJL 可以到達的樓層數。
輸入輸出樣例
輸入 #1復制
15 4 7 9
輸出 #1復制
9
輸入 #2復制
33333333333 99005 99002 100000
輸出 #2復制
33302114671
說明/提示
可以到達的樓層有：1,5,8,9,10,12,13,14,15。
1≤h≤263?1，1≤x,y,z≤105。
代碼實現：
#include<bits/stdc++.h>
#define int long long
int head[2000005],edgeCount;
struct EdgeData{
int target;
int next;
int weight;
};
EdgeData edges[2000005];
void addEdge(int fromNode,int toNode,int weight) {
edgeCount++;
edges[edgeCount].target=toNode;
edges[edgeCount].weight=weight;
edges[edgeCount].next=head[fromNode];
head[fromNode]=edgeCount;
}
int distance[1000005];
bool visited[1000005];
struct QueueNode{
int distance;
int position;
bool operator < (const QueueNode &x) const {
return x.distance < distance;
}
};
std::priority_queue<QueueNode> priorityQueue;
void dijkstra(int start) {
memset(distance,0x3f,sizeof(distance));
distance[start]=0;
priorityQueue.push((QueueNode){0,start});
while(!priorityQueue.empty()) {
QueueNode current=priorityQueue.top();
priorityQueue.pop();
int currentNode=current.position;
if(visited[currentNode]) continue;
visited[currentNode]=1;
for(int i=head[currentNode];i;i=edges[i].next) {
int nextNode=edges[i].target;
if(distance[nextNode]>distance[currentNode]+edges[i].weight) {
distance[nextNode]=distance[currentNode]+edges[i].weight;
priorityQueue.push((QueueNode){distance[nextNode],nextNode});
}
}
}
}
int maxHeight,modValue,stepY,stepZ,result=0;
signed main() {
std::cin>>maxHeight>>modValue>>stepY>>stepZ;
//特判
if(modValue==1 || stepY==1 || stepZ==1) {
std::cout<<maxHeight;
return 0;
}
maxHeight--;
//建圖
for(int i=0;i<modValue;i++) {
addEdge(i,(i+stepZ)%modValue,stepZ);
addEdge(i,(i+stepY)%modValue,stepY);
}
dijkstra(1);
for(int i=0;i<modValue;i++) {
if(maxHeight>=distance[i]) result+=(maxHeight-distance[i])/modValue+1;
//注意這個地方要多加一條判斷
}
std::cout<<result;
return 0;
}
