#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 ;
// cout<<node<<" "<<place<<" " <<dist<<"+\n" ;
q.pop();
if(node==-1)
continue;
int j = 1;
if(!p[node]) continue;
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()
{
//freopen("in.in" , "r", stdin) ;
cin>>n>>m ;
for(int i = 0 ; i < N ;i++)
b[i] = n;
memset(bn , -1 , sizeof bn) ;
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 ;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
3832 KB |
Output is correct |
2 |
Correct |
6 ms |
3832 KB |
Output is correct |
3 |
Correct |
6 ms |
3832 KB |
Output is correct |
4 |
Correct |
7 ms |
3832 KB |
Output is correct |
5 |
Correct |
6 ms |
3832 KB |
Output is correct |
6 |
Correct |
6 ms |
3832 KB |
Output is correct |
7 |
Correct |
7 ms |
3832 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
3832 KB |
Output is correct |
2 |
Correct |
7 ms |
3832 KB |
Output is correct |
3 |
Correct |
7 ms |
3832 KB |
Output is correct |
4 |
Correct |
6 ms |
3832 KB |
Output is correct |
5 |
Correct |
6 ms |
3832 KB |
Output is correct |
6 |
Correct |
6 ms |
3836 KB |
Output is correct |
7 |
Correct |
6 ms |
3836 KB |
Output is correct |
8 |
Correct |
6 ms |
3832 KB |
Output is correct |
9 |
Correct |
7 ms |
3832 KB |
Output is correct |
10 |
Incorrect |
7 ms |
3832 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
3832 KB |
Output is correct |
2 |
Correct |
7 ms |
3832 KB |
Output is correct |
3 |
Correct |
7 ms |
3832 KB |
Output is correct |
4 |
Correct |
6 ms |
3832 KB |
Output is correct |
5 |
Correct |
7 ms |
3832 KB |
Output is correct |
6 |
Correct |
7 ms |
3832 KB |
Output is correct |
7 |
Correct |
8 ms |
3832 KB |
Output is correct |
8 |
Correct |
6 ms |
3832 KB |
Output is correct |
9 |
Correct |
7 ms |
3832 KB |
Output is correct |
10 |
Incorrect |
7 ms |
3832 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
3832 KB |
Output is correct |
2 |
Correct |
7 ms |
3836 KB |
Output is correct |
3 |
Correct |
7 ms |
3832 KB |
Output is correct |
4 |
Correct |
7 ms |
3832 KB |
Output is correct |
5 |
Correct |
6 ms |
3832 KB |
Output is correct |
6 |
Correct |
7 ms |
3832 KB |
Output is correct |
7 |
Correct |
8 ms |
3832 KB |
Output is correct |
8 |
Correct |
6 ms |
3832 KB |
Output is correct |
9 |
Correct |
6 ms |
3832 KB |
Output is correct |
10 |
Incorrect |
7 ms |
3832 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
3832 KB |
Output is correct |
2 |
Correct |
7 ms |
3832 KB |
Output is correct |
3 |
Correct |
6 ms |
3832 KB |
Output is correct |
4 |
Correct |
6 ms |
3832 KB |
Output is correct |
5 |
Correct |
7 ms |
3832 KB |
Output is correct |
6 |
Correct |
6 ms |
3832 KB |
Output is correct |
7 |
Correct |
7 ms |
3832 KB |
Output is correct |
8 |
Correct |
7 ms |
3832 KB |
Output is correct |
9 |
Correct |
6 ms |
3832 KB |
Output is correct |
10 |
Incorrect |
7 ms |
3832 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |