#include <algorithm>
#include <bits/stdc++.h>
#include <cassert>
#include <vector>
using namespace std;
#define ll int
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair
#define pb push_back
#define INF (ll)1e18
ll MOD = 1e9+7;
void solve(){
ll n, m; cin >> n >> m;
vector<vector<pair<ll, ll>>> avail(n);
vector<pair<ll, ll>> d(m);
for (ll i=0; i<m; i++){
ll x, p; cin >> x >> p;
d[i] = {x, p};
avail[x].push_back({p, i});
}
vector<vector<bool>> vis(n, vector<bool>(n+1));
vector<ll> dist(n, INF); queue<tuple<ll, ll, ll>> que;
que.push({0, d[0].ff, 0});
while (!que.empty()){
auto [w, x, i]=que.front(); que.pop();
if (vis[x][d[i].ss]) continue;
vis[x][d[i].ss]=1; dist[i]=min(dist[i], w);
if (x-d[i].ss>=0 and !vis[x-d[i].ss][d[i].ss]) que.push({w+1, x-d[i].ss, i});
if (x+d[i].ss<n and !vis[x+d[i].ss][d[i].ss]) que.push({w+1, x+d[i].ss, i});
for (auto [p, ind]:avail[x]){
dist[ind]=min(dist[ind], w);
if (x-d[ind].ss>=0 and !vis[x-d[ind].ss][d[ind].ss]) que.push({w+1, x-d[ind].ss, ind});
if (x+d[ind].ss<n and !vis[x+d[ind].ss][d[ind].ss]) que.push({w+1, x+d[ind].ss, ind});
}
}
cout << (dist[1]!=INF?dist[1]:-1) << ln;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(nullptr);
#ifdef LOCAL
auto start = chrono::high_resolution_clock::now();
#endif
ll testc=1;
// cin >> testc;
for (ll __c=1; __c<=testc; __c++) solve();
#ifdef LOCAL
auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
#endif
}
# | 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... |