#include<bits/stdc++.h>
using namespace std ;
const int N = 3e5 + 7 ;
int n , m ;
int b[N] , p[N] , d[N];
vector<pair<int , int > > adj[N] ;
int dijkstra(int s)
{
memset(d , -1 , sizeof d) ;
priority_queue<pair<int , int > > q ;
q.push({0 , b[0]}) ;
d[ b[0] ] = 0;
while(q.size())
{
int node = q .top().second ;
int dist = -q.top().first ;
q.pop();
for(auto u : adj[node])
{
if(d[u.first]==-1 || dist + u.second < d[u.first])
{
d[u.first] = dist + u.second ;
q.push({-d[u.first] , u.first}) ;
}
}
}
return d[1] ;
}
int main()
{
// freopen("in.in" , "r", stdin) ;
cin>>n>>m ;
for(int i= 0 ; i < m ; i++)
{
int A , B;
cin>>A>>B ;
b[ A ] = i;
p[ A] = B ;
if(!B)
continue;
for(int j = 0 ; j < n ; j++)
{
if(A==j)
continue;
if(j==A)
continue;
if(abs(A-j)%B==0)
{
adj[A].push_back({j , abs(A-j)/B});
}
}
}
cout<<dijkstra(b[0]);
return 0 ;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
8568 KB |
Output is correct |
2 |
Correct |
9 ms |
8568 KB |
Output is correct |
3 |
Correct |
9 ms |
8568 KB |
Output is correct |
4 |
Correct |
10 ms |
8568 KB |
Output is correct |
5 |
Incorrect |
9 ms |
8568 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
8568 KB |
Output is correct |
2 |
Correct |
10 ms |
8568 KB |
Output is correct |
3 |
Correct |
11 ms |
8568 KB |
Output is correct |
4 |
Correct |
11 ms |
8564 KB |
Output is correct |
5 |
Incorrect |
10 ms |
8568 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
8568 KB |
Output is correct |
2 |
Correct |
10 ms |
8568 KB |
Output is correct |
3 |
Correct |
9 ms |
8568 KB |
Output is correct |
4 |
Correct |
10 ms |
8568 KB |
Output is correct |
5 |
Incorrect |
9 ms |
8568 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
8568 KB |
Output is correct |
2 |
Correct |
10 ms |
8568 KB |
Output is correct |
3 |
Correct |
10 ms |
8568 KB |
Output is correct |
4 |
Correct |
9 ms |
8568 KB |
Output is correct |
5 |
Incorrect |
10 ms |
8568 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
8568 KB |
Output is correct |
2 |
Correct |
12 ms |
8568 KB |
Output is correct |
3 |
Correct |
10 ms |
8568 KB |
Output is correct |
4 |
Correct |
9 ms |
8568 KB |
Output is correct |
5 |
Incorrect |
9 ms |
8572 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |