#include<bits/stdc++.h>
#define ll long long
#define fi first
#define sec second
#define pb push_back
#define pqueue priority_queue
#define int long long
#define pii pair<int,int>
#define supercepat ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0);
using namespace std;
int tc,ans=0,n,m;
int b[30005],p[30005];
vector<int> vec[30005];
pqueue<pii> a;
int dis[30005];
void djikstra(int x){
a.push(pii(0,x));
while(!a.empty()){
int idx=a.top().sec; // nomor gedung
if(idx==b[1]) break;
int dist=-1*a.top().fi;
if(dis[idx]<dist){
continue;
}
else{
for(auto i : vec[idx]){
for(int j = idx+p[i];j<n;j+=p[i]){
if(dis[j]>dist+(abs(j-idx)/p[i])){
dis[j]=dist+(abs(j-idx)/p[i]);
a.push(pii(-1*dis[j],j));
}
}
for(int j = idx-p[i];j>=0;j-=p[i]){
if(dis[j]>dist+(abs(j-idx)/p[i])){
dis[j]=dist+(abs(j-idx)/p[i]);
a.push(pii(-1*dis[j],j));
}
}
}
}
a.pop();
}
}
main(){
supercepat;
cin>>n>>m;
for(int i=0;i<n;i++) dis[i]=INT_MAX;
for(int i=0;i<m;i++){
cin>>b[i]>>p[i];
vec[b[i]].pb(i);
}
dis[b[0]]=0;
djikstra(b[0]);
if(dis[b[1]]==INT_MAX) cout<<-1<<endl;
else cout<<dis[b[1]]<<endl;
}
Compilation message
skyscraper.cpp:44:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
44 | main(){
| ^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
980 KB |
Output is correct |
5 |
Correct |
1 ms |
980 KB |
Output is correct |
6 |
Correct |
1 ms |
980 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
980 KB |
Output is correct |
5 |
Correct |
1 ms |
980 KB |
Output is correct |
6 |
Correct |
1 ms |
980 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
8 |
Correct |
1 ms |
980 KB |
Output is correct |
9 |
Correct |
1 ms |
980 KB |
Output is correct |
10 |
Correct |
1 ms |
1024 KB |
Output is correct |
11 |
Correct |
1 ms |
1108 KB |
Output is correct |
12 |
Correct |
1 ms |
1108 KB |
Output is correct |
13 |
Correct |
2 ms |
1108 KB |
Output is correct |
14 |
Execution timed out |
1084 ms |
1108 KB |
Time limit exceeded |
15 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
980 KB |
Output is correct |
5 |
Correct |
1 ms |
980 KB |
Output is correct |
6 |
Correct |
1 ms |
980 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
8 |
Correct |
1 ms |
980 KB |
Output is correct |
9 |
Correct |
1 ms |
980 KB |
Output is correct |
10 |
Correct |
1 ms |
1036 KB |
Output is correct |
11 |
Correct |
1 ms |
1108 KB |
Output is correct |
12 |
Correct |
1 ms |
1108 KB |
Output is correct |
13 |
Correct |
2 ms |
1108 KB |
Output is correct |
14 |
Execution timed out |
1093 ms |
1044 KB |
Time limit exceeded |
15 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
980 KB |
Output is correct |
5 |
Correct |
1 ms |
980 KB |
Output is correct |
6 |
Correct |
1 ms |
1036 KB |
Output is correct |
7 |
Correct |
1 ms |
1032 KB |
Output is correct |
8 |
Correct |
1 ms |
980 KB |
Output is correct |
9 |
Correct |
1 ms |
980 KB |
Output is correct |
10 |
Correct |
1 ms |
980 KB |
Output is correct |
11 |
Correct |
1 ms |
1108 KB |
Output is correct |
12 |
Correct |
1 ms |
1108 KB |
Output is correct |
13 |
Correct |
2 ms |
1108 KB |
Output is correct |
14 |
Execution timed out |
1084 ms |
1108 KB |
Time limit exceeded |
15 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
980 KB |
Output is correct |
5 |
Correct |
1 ms |
980 KB |
Output is correct |
6 |
Correct |
1 ms |
980 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
8 |
Correct |
1 ms |
1032 KB |
Output is correct |
9 |
Correct |
1 ms |
1032 KB |
Output is correct |
10 |
Correct |
1 ms |
980 KB |
Output is correct |
11 |
Correct |
1 ms |
1108 KB |
Output is correct |
12 |
Correct |
1 ms |
1232 KB |
Output is correct |
13 |
Correct |
2 ms |
1040 KB |
Output is correct |
14 |
Execution timed out |
1074 ms |
1108 KB |
Time limit exceeded |
15 |
Halted |
0 ms |
0 KB |
- |