#include<bits/stdc++.h>
using namespace std ;
const int N = 3e5 + 7 ;
int n , m ;
int b[N] , bn[N] , p[N] , d[N];
int dijkstra()
{
memset(d , -1 , sizeof d) ;
priority_queue<pair<int , int > > q ;
q.push({0 , b[0]}) ;
d[ b[0] ] = 0;
while(q.size())
{
int place = q .top().second ;
int node = bn[place] ;
int dist = -q.top().first ;
q.pop();
if(!p[node])
continue;
int j = 1;
for(int i = place + p[node] ; i < n ; i+=p[node] , j++)
{
if(d[i]==-1 || dist + j < d[i])
{
d[i] = dist + j ;
q.push({-d[i] , i}) ;
}
}
j = 1 ;
for(int i = place - p[node] ; i >= 0 ; i-=p[node] , j++)
{
if(d[i]==-1 || dist + j < d[i])
{
d[i] = dist + j ;
q.push({-d[i] , i}) ;
}
}
}
return d[ b[1] ] ;
}
int main()
{
//reopen("in.in" , "r", stdin) ;
cin>>n>>m ;
for(int i = 0 ; i < N ;i++)
b[i] = n;
for(int i= 0 ; i < m ; i++)
{
int A , B;
cin>>A>>B ;
b[ i ] = A;
bn[A] = i ;
p[i] = B ;
}
cout<<dijkstra();
return 0 ;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
2680 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
2680 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
2680 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
2680 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
2680 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |