#include <bits/stdc++.h>
#define ll long long
#define int long long
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define lc (id << 1)
#define rc ((id << 1) ^ 1)
using namespace std;
const long long mod = 1e9 + 7, maxn = 3e4 + 9, base = 1e6 + 7;
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
int n,m,d[maxn];
vector<pair<int,int>> dog;
int32_t main()
{
//fast_io;
cin >> n >> m;
for(int i = 1; i <= m;i++)
{
int bi,pi;
cin >> bi >>pi;
dog.push_back({bi + 1 , pi});
}
priority_queue< pair<int,int> , vector < pair<int,int>> ,greater<pair<int,int>> > q;
q.push({ 0 , 0});
bitset<maxn> mark;
while (q.size())
{
pair<int, int> aa = q.top();
q.pop();
if(mark[aa.second]) continue;
d[aa.second] = aa.first;
mark[aa.second] = true;
int v = aa.second;
for(int i = 0; i < m;i++)
if((dog[i].first % dog[v].second) == (dog[v].first % dog[v].second))
if(!mark[i])
q.push({d[v] + (abs(dog[i].first - dog[v].first) / dog[v].second) , i});
}
if(mark[1])
cout << d[1] << "\n";
else
cout << "-1\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |