#include<stdio.h>
#include<math.h>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>con[30010];
typedef pair<int,int> ppair;
struct data{
int val,x,y;
bool operator<(const data&r)const{
return val>r.val;
}
}b;
priority_queue<data>q;
int sw,n,m,root,d[30010][200],s,pos,ch[30010][200];
struct data2{
int x,p;
}a[30010];
int main()
{
int i,j,val,x,y;
scanf("%d %d",&n,&m);
root=sqrt(n);
for(i=0;i<m;i++){scanf("%d %d",&a[i].x,&a[i].p); con[a[i].x].push_back(a[i].p);}
d[a[0].x][a[0].p]=0;
b.val=0, b.x=a[0].x, b.y=a[0].p, q.push(b);
while(1)
{
while(q.size() && ch[q.top().x][q.top().y]) q.pop();
if(q.size()==0){sw=1; break;}
val=q.top().val; x=q.top().x; y=q.top().y; ch[x][y]=1; q.pop();
if(x==a[1].x) break;
for(i=0;i<con[x].size();i++){
b.val=val; b.x=x; b.y=con[x][i];
q.push(b);
}
if(x+y<n){
b.val=val+1; b.x=x+y; b.y=y; q.push(b);
}
if(x-y>=0){
b.val=val+1; b.x=x-y; b.y=y; q.push(b);
}
}
if(sw) printf("-1");
else printf("%d",val);
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
49432 KB |
Output is correct |
2 |
Correct |
0 ms |
49432 KB |
Output is correct |
3 |
Correct |
0 ms |
49432 KB |
Output is correct |
4 |
Correct |
0 ms |
49432 KB |
Output is correct |
5 |
Correct |
1 ms |
49432 KB |
Output is correct |
6 |
Correct |
0 ms |
49432 KB |
Output is correct |
7 |
Correct |
0 ms |
49432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
49432 KB |
Output is correct |
2 |
Correct |
0 ms |
49432 KB |
Output is correct |
3 |
Correct |
0 ms |
49432 KB |
Output is correct |
4 |
Correct |
1 ms |
49432 KB |
Output is correct |
5 |
Correct |
0 ms |
49432 KB |
Output is correct |
6 |
Correct |
0 ms |
49432 KB |
Output is correct |
7 |
Correct |
0 ms |
49432 KB |
Output is correct |
8 |
Correct |
1 ms |
49432 KB |
Output is correct |
9 |
Correct |
1 ms |
49432 KB |
Output is correct |
10 |
Correct |
0 ms |
49432 KB |
Output is correct |
11 |
Correct |
0 ms |
49432 KB |
Output is correct |
12 |
Correct |
0 ms |
49432 KB |
Output is correct |
13 |
Correct |
0 ms |
49432 KB |
Output is correct |
14 |
Correct |
13 ms |
49640 KB |
Output is correct |
15 |
Correct |
7 ms |
49640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
49432 KB |
Output is correct |
2 |
Correct |
0 ms |
49432 KB |
Output is correct |
3 |
Correct |
0 ms |
49432 KB |
Output is correct |
4 |
Correct |
0 ms |
49432 KB |
Output is correct |
5 |
Correct |
0 ms |
49432 KB |
Output is correct |
6 |
Correct |
0 ms |
49432 KB |
Output is correct |
7 |
Correct |
0 ms |
49432 KB |
Output is correct |
8 |
Correct |
0 ms |
49432 KB |
Output is correct |
9 |
Correct |
0 ms |
49432 KB |
Output is correct |
10 |
Correct |
0 ms |
49432 KB |
Output is correct |
11 |
Correct |
0 ms |
49432 KB |
Output is correct |
12 |
Correct |
0 ms |
49432 KB |
Output is correct |
13 |
Correct |
2 ms |
49432 KB |
Output is correct |
14 |
Correct |
15 ms |
49640 KB |
Output is correct |
15 |
Correct |
11 ms |
49640 KB |
Output is correct |
16 |
Correct |
0 ms |
49432 KB |
Output is correct |
17 |
Correct |
0 ms |
49432 KB |
Output is correct |
18 |
Correct |
0 ms |
49432 KB |
Output is correct |
19 |
Correct |
0 ms |
49432 KB |
Output is correct |
20 |
Correct |
0 ms |
49432 KB |
Output is correct |
21 |
Correct |
0 ms |
49432 KB |
Output is correct |
22 |
Correct |
0 ms |
49432 KB |
Output is correct |
23 |
Correct |
0 ms |
49432 KB |
Output is correct |
24 |
Correct |
4 ms |
49432 KB |
Output is correct |
25 |
Correct |
0 ms |
49432 KB |
Output is correct |
26 |
Correct |
0 ms |
49432 KB |
Output is correct |
27 |
Correct |
0 ms |
49432 KB |
Output is correct |
28 |
Incorrect |
0 ms |
49432 KB |
Output isn't correct |
29 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
49432 KB |
Output is correct |
2 |
Correct |
0 ms |
49432 KB |
Output is correct |
3 |
Correct |
0 ms |
49432 KB |
Output is correct |
4 |
Correct |
0 ms |
49432 KB |
Output is correct |
5 |
Correct |
0 ms |
49432 KB |
Output is correct |
6 |
Correct |
0 ms |
49432 KB |
Output is correct |
7 |
Correct |
0 ms |
49432 KB |
Output is correct |
8 |
Correct |
0 ms |
49432 KB |
Output is correct |
9 |
Correct |
0 ms |
49432 KB |
Output is correct |
10 |
Correct |
1 ms |
49432 KB |
Output is correct |
11 |
Correct |
0 ms |
49432 KB |
Output is correct |
12 |
Correct |
0 ms |
49432 KB |
Output is correct |
13 |
Correct |
1 ms |
49432 KB |
Output is correct |
14 |
Correct |
15 ms |
49640 KB |
Output is correct |
15 |
Correct |
7 ms |
49640 KB |
Output is correct |
16 |
Correct |
0 ms |
49432 KB |
Output is correct |
17 |
Correct |
0 ms |
49432 KB |
Output is correct |
18 |
Correct |
0 ms |
49432 KB |
Output is correct |
19 |
Correct |
0 ms |
49432 KB |
Output is correct |
20 |
Correct |
0 ms |
49432 KB |
Output is correct |
21 |
Correct |
0 ms |
49432 KB |
Output is correct |
22 |
Correct |
0 ms |
49432 KB |
Output is correct |
23 |
Correct |
0 ms |
49432 KB |
Output is correct |
24 |
Correct |
4 ms |
49432 KB |
Output is correct |
25 |
Correct |
0 ms |
49432 KB |
Output is correct |
26 |
Correct |
0 ms |
49432 KB |
Output is correct |
27 |
Correct |
0 ms |
49432 KB |
Output is correct |
28 |
Incorrect |
0 ms |
49432 KB |
Output isn't correct |
29 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
49432 KB |
Output is correct |
2 |
Correct |
0 ms |
49432 KB |
Output is correct |
3 |
Correct |
0 ms |
49432 KB |
Output is correct |
4 |
Correct |
0 ms |
49432 KB |
Output is correct |
5 |
Correct |
0 ms |
49432 KB |
Output is correct |
6 |
Correct |
0 ms |
49432 KB |
Output is correct |
7 |
Correct |
0 ms |
49432 KB |
Output is correct |
8 |
Correct |
0 ms |
49432 KB |
Output is correct |
9 |
Correct |
0 ms |
49432 KB |
Output is correct |
10 |
Correct |
1 ms |
49432 KB |
Output is correct |
11 |
Correct |
0 ms |
49432 KB |
Output is correct |
12 |
Correct |
0 ms |
49432 KB |
Output is correct |
13 |
Correct |
0 ms |
49432 KB |
Output is correct |
14 |
Correct |
15 ms |
49640 KB |
Output is correct |
15 |
Correct |
7 ms |
49640 KB |
Output is correct |
16 |
Correct |
0 ms |
49432 KB |
Output is correct |
17 |
Correct |
0 ms |
49432 KB |
Output is correct |
18 |
Correct |
0 ms |
49432 KB |
Output is correct |
19 |
Correct |
0 ms |
49432 KB |
Output is correct |
20 |
Correct |
2 ms |
49432 KB |
Output is correct |
21 |
Correct |
1 ms |
49432 KB |
Output is correct |
22 |
Correct |
0 ms |
49432 KB |
Output is correct |
23 |
Correct |
0 ms |
49432 KB |
Output is correct |
24 |
Correct |
4 ms |
49432 KB |
Output is correct |
25 |
Correct |
0 ms |
49432 KB |
Output is correct |
26 |
Correct |
2 ms |
49432 KB |
Output is correct |
27 |
Correct |
0 ms |
49432 KB |
Output is correct |
28 |
Incorrect |
0 ms |
49432 KB |
Output isn't correct |
29 |
Halted |
0 ms |
0 KB |
- |