| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1191403 | Ardelion | Jakarta Skyscrapers (APIO15_skyscraper) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
using namespace std;
//#define int long long
#define ll long long
#define X first
#define Y second
#define lc (id<<1)
#define rc (lc|1)
#define mid ((l+r+1)>>1)
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define sep ' '
#define endl "\n"
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define FileIO freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define all(x) x.begin(), x.end()
#define ret(x) {cout << x << endl; return;}
typedef pair<int, int> pii;
typedef pair<ll , ll > pll;
const int N = 3e4+13;
const int LOG = 23;
const int MOD = 1e9 + 7; //998244353; //1e9+9;
const int INF = 1e9; //1e18;
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
ll md(ll x) {x%=MOD; return (x < 0 ? x+MOD : x);}
ll GCD(ll _a, ll _b) { return (!_b ? _a : GCD(_b, _a % _b)); }
ll POW(ll _a, ll _b) { return !_b ? 1 : ((_b & 1 ? _a : 1) * POW(_a * _a % MOD, _b / 2)) % MOD;}
int n, m, s, f;
int dist[N][N], P[N];
vector<int> b[N];
void BFS() {
deque<pii> q;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
dist[i][j] = INF;
}
}
dist[s][0] = 0;
q.push_back(mp(s, 0));
pii p;
while(!q.empty()) {
p = q.front();
q.pop_front();
for(int d : b[p.X]) {
if(dist[p.X][d] > dist[p.X][p.Y]) {
dist[p.X][d] = dist[p.X][p.Y];
q.push_front(mp(p.X, d));
}
}
if(p.X - P[p.Y] >= 0 && dist[p.X-P[p.Y]][p.Y] > dist[p.X][p.Y] + 1) {
dist[p.X-P[p.Y]][p.Y] = dist[p.X][p.Y] + 1;
q.push_back(mp(p.X-P[p.Y], p.Y));
}
if(p.X + P[p.Y] < n && dist[p.X+P[p.Y]][p.Y] > dist[p.X][p.Y] + 1) {
dist[p.X+P[p.Y]][p.Y] = dist[p.X][p.Y] + 1;
q.push_back(mp(p.X+P[p.Y], p.Y));
}
}
}
void F() {
cin >> n >> m;
int x;
for(int i = 0; i < m; i++) {
cin >> x >> P[i];
if(i == 0) s = x;
else if(i == 1) f = x;
b[x].pb(i);
}
BFS();
cout << (dist[f][1] == INF ? -1 : dist[f][1]);
}
int32_t main() {
migmig;
//PREP();
int t=1;
//cin >> t;
while(t--)
F();
return 0;
}