이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/// dwuy: _,\,,,_\,__,\,,_
#include <bits/stdc++.h>
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) int32_t(s.length())
#define MASK(k)(1LL<<(k))
#define TASK ""
using namespace std;
typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;
const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 30005;
int n, m;
int pw[MX];
int pos[MX];
vector<int> G[MX];
bitset<MX> vist[MX];
void nhap(){
cin >> n >> m;
for(int i=1; i<=m; i++){
cin >> pos[i] >> pw[i];
G[pos[i]].push_back(pw[i]);
}
}
void solve(){
queue<tuple<int, int, int>> Q;
Q.push({pos[1], pw[1], 0});
int ans = -1;
while(Q.size()){
int u, p, d;
tie(u, p, d) = Q.front();
Q.pop();
if(u == pos[2]){
ans = d;
break;
}
if(u-p>0 && !vist[u-p][p]){
vist[u-p][p] = 1;
Q.push({u-p, p, d+1});
}
if(u+p<n && !vist[u+p][p]){
vist[u+p][p] = 1;
Q.push({u+p, p, d+1});
}
for(int p: G[u]){
vist[u][p] = 1;
if(u-p>0 && !vist[u-p][p]){
vist[u-p][p] = 1;
Q.push({u-p, p, d+1});
}
if(u+p<n && !vist[u+p][p]){
vist[u+p][p] = 1;
Q.push({u+p, p, d+1});
}
}
}
cout << ans;
}
int32_t main(){
fastIO;
//file(TASK);
nhap();
solve();
return 0;
}
# | 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... |