#include<bits/stdc++.h>
using namespace std;
#define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
int t, n, m, k, b[30010], p[30010];
int crd[30010];
int d[30010];
bool v[30010];
vector<pii> g[30010];
bool dog[30010];
void dijkstra(){
multiset<pii> ms;
ms.insert({d[crd[1] ], crd[1]});
while(!ms.empty()){
auto f=*ms.begin(); ms.erase(ms.begin());
int nod=f.sc;
v[nod]=true;
//cout<<nod<<"y\n";
if(nod==crd[2]){return;}
for(auto pr:g[nod]){
int u=pr.ft, c=pr.sc;
if(v[u]){continue;}
//cout<<u<<" "<<c<<"x\n";
auto it=ms.find({d[u], u});
if(it!=ms.end()){
ms.erase(it);
d[u]=min(d[u], d[nod]+c);
ms.insert({d[u], u});
}
else{
d[u]=d[nod]+c;
ms.insert({d[u], u} );
}
}
}
return;
}
map<pii, bool> h;
int up[30010], down[30010];
void add_chain(int b, int p){
for(int i=b-p; (i>=1) && (i>=down[p]) ; i-=p){
if(dog[i]){g[b].pb({i, abs(i-b)/p });}
}
down[p]=max(down[p], b);
for(int i=b+p; (i<=n) && (up[p]>=i); i+=p){
if(dog[i]){g[b].pb({i, abs(i-b)/p });}
}
up[p]=min(up[p], b);
}
int32_t main(){
INIT
cin>>n>>m;
for(int i=1; i<=n; i++){d[i]=-1; up[i]=n+1; down[i]=0; }
for(int i=1; i<=m; i++){
cin>>b[i]>>p[i]; b[i]++;
crd[i ]=b[i];
dog[b[i] ]=true;
}
for(int i=1; i<=m; i++){
add_chain(b[i], p[i]);
}
d[crd[1] ]=0;
dijkstra();
cout<<d[crd[2] ];
/*for(int i=1; i<=n; i++){
for(auto u:g[i]){
cout<<u.ft<<" ";
}
cout<<"\n";
}*/
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1152 KB |
Output is correct |
2 |
Correct |
1 ms |
1132 KB |
Output is correct |
3 |
Correct |
1 ms |
1132 KB |
Output is correct |
4 |
Correct |
1 ms |
1132 KB |
Output is correct |
5 |
Correct |
1 ms |
1132 KB |
Output is correct |
6 |
Correct |
2 ms |
1132 KB |
Output is correct |
7 |
Correct |
1 ms |
1132 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1132 KB |
Output is correct |
2 |
Correct |
1 ms |
1132 KB |
Output is correct |
3 |
Correct |
1 ms |
1132 KB |
Output is correct |
4 |
Correct |
1 ms |
1152 KB |
Output is correct |
5 |
Correct |
1 ms |
1132 KB |
Output is correct |
6 |
Correct |
1 ms |
1132 KB |
Output is correct |
7 |
Correct |
1 ms |
1132 KB |
Output is correct |
8 |
Correct |
1 ms |
1132 KB |
Output is correct |
9 |
Incorrect |
1 ms |
1132 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1132 KB |
Output is correct |
2 |
Correct |
1 ms |
1132 KB |
Output is correct |
3 |
Correct |
1 ms |
1132 KB |
Output is correct |
4 |
Correct |
1 ms |
1132 KB |
Output is correct |
5 |
Correct |
1 ms |
1132 KB |
Output is correct |
6 |
Correct |
1 ms |
1132 KB |
Output is correct |
7 |
Correct |
1 ms |
1132 KB |
Output is correct |
8 |
Correct |
1 ms |
1132 KB |
Output is correct |
9 |
Incorrect |
1 ms |
1132 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
1132 KB |
Output is correct |
2 |
Correct |
1 ms |
1132 KB |
Output is correct |
3 |
Correct |
1 ms |
1132 KB |
Output is correct |
4 |
Correct |
1 ms |
1132 KB |
Output is correct |
5 |
Correct |
1 ms |
1132 KB |
Output is correct |
6 |
Correct |
1 ms |
1132 KB |
Output is correct |
7 |
Correct |
1 ms |
1132 KB |
Output is correct |
8 |
Correct |
1 ms |
1132 KB |
Output is correct |
9 |
Incorrect |
2 ms |
1132 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1132 KB |
Output is correct |
2 |
Correct |
1 ms |
1132 KB |
Output is correct |
3 |
Correct |
1 ms |
1132 KB |
Output is correct |
4 |
Correct |
1 ms |
1132 KB |
Output is correct |
5 |
Correct |
1 ms |
1132 KB |
Output is correct |
6 |
Correct |
1 ms |
1132 KB |
Output is correct |
7 |
Correct |
1 ms |
1132 KB |
Output is correct |
8 |
Correct |
1 ms |
1132 KB |
Output is correct |
9 |
Incorrect |
1 ms |
1132 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |