#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
vector<vector<ll>> smallpowers; //on given skyscraper
vector<vector<pair<ll,ll>>> adjlist; //weight, node
ll n;
ll INF = 1e18;
ll dijkstra(ll startloc, ll endloc){
ll start = startloc;
vector<vector<ll>> distances(n, vector<ll>(ll(sqrt(n))+1, INF));
distances[start][0]=0;
priority_queue<pair<ll,pair<ll,ll>>,vector<pair<ll,pair<ll,ll>>>,less<pair<ll,pair<ll,ll>>>> pq;
pq.push({0,{0,0}});
while (pq.size()>0){
auto f = pq.top();
pq.pop();
if (distances[f.second.first][f.second.second]<f.first){
continue;
}
ll curdist = f.first;
ll curnode = f.second.first;
ll curind = f.second.second;
if (curind==0){
// we can go to a doge with cost 0
for (ll i : smallpowers[curnode]){
if (distances[curnode][i]>curdist){
distances[curnode][i]=curdist;
pq.push({distances[curnode][i],{curnode,i}});
}
}
// or we can jump skyscrapers
for (auto p : adjlist[curnode]){
if (distances[p.second][0]>curdist+p.first){
distances[p.second][0]=curdist+p.first;
pq.push({distances[p.second][0],{p.second,0}});
}
}
} else {
//we can go to central node with cost 0
if (distances[curnode][0]>curdist){
distances[curnode][0]=curdist;
pq.push({distances[curnode][0],{curnode,0}});
}
//or we can go to an adjacent node
if (curnode-curind>=0&&distances[curnode-curind][curind]>curdist+1){
distances[curnode-curind][curind]=curdist+1;
pq.push({distances[curnode-curind][curind],{curnode-curind,curind}});
}
if (curnode+curind<n&&distances[curnode+curind][curind]>curdist+1){
distances[curnode+curind][curind]=curdist+1;
pq.push({distances[curnode+curind][curind],{curnode+curind,curind}});
}
}
}
return distances[endloc][0];
}
int main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
ll m;
cin>>n>>m;
ll sqrtv = sqrt(n);
smallpowers.resize(n);
adjlist.resize(n);
ll startloc = 0;
ll endloc = 0;
for (ll i = 0; i<m; i++){
ll b,p;
cin>>b>>p;
if (i==0){
startloc=b;
}
if (i==1){
endloc=b;
}
//skyscraper b, moves p
if (p<sqrtv){
smallpowers[b].push_back(p);
} else {
ll cnt = 0;
for (ll x = b+p; x<n; x+=p){
cnt++;
adjlist[b].push_back({cnt,x});
}
cnt = 0;
for (ll x = b-p; x>=0; x-=p){
cnt++;
adjlist[b].push_back({cnt,x});
}
}
}
ll d = dijkstra(startloc,endloc);
if (d==INF){
cout<<-1<<'\n';
} else {
cout<<d<<'\n';
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |