This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
using ll = long long;
using ld = long double;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) (int)x.size()
#define endl '\n'
const int mod = 1e9 + 7;
const int inf = 1e9 + 5;
const ll linf = 9e18 + 5;
int n, m;
const int N = 2e3 + 5;
int arr[N][2];
int w[N][N];
int dist[N];
void init() {
}
void input() {
cin >> m >> n;
for (int i = 1; i <= n; i++) {
cin >> arr[i][0] >> arr[i][1];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (abs(arr[j][0] - arr[i][0]) % arr[i][1] == 0) {
w[i][j] = abs(arr[j][0] - arr[i][0]) / arr[i][1];
}
else {
w[i][j] = inf;
}
}
}
}
void dijk() {
set<pair<int, int>> dists;
for (int i = 1; i <= n; i++) {
dist[i] = inf;
dists.insert(mp(dist[i], i));
}
dists.erase(mp(dist[1], 1));
dist[1] = 0;
dists.insert(mp(dist[1], 1));
while (!dists.empty()) {
int u = dists.begin()->se;
dists.erase(dists.begin());
for (int v = 1; v <= n; v++) {
if (dist[v] > dist[u] + w[u][v]) {
dists.erase(mp(dist[v], v));
dist[v] = dist[u] + w[u][v];
dists.insert(mp(dist[v], v));
}
}
}
}
void solve() {
dijk();
if (dist[2] == inf) {
cout << -1;
}
else {
cout << dist[2];
}
}
void output() {
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int number_of_testcases = 1;
//cin >> number_of_testcases;
while (number_of_testcases--) {
init();
input();
solve();
output();
}
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... |