#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef pair <ll, ll> pii;
const int N = 3e4 + 7, SN = 2e3 + 7;
ll inf = 1e18;
int n, m;
ll a[N], b[N], dis[N], ed[SN][SN];
vector <pii> v[SN];
int main () {
cin >> n >> m;
for (int i = 0; i < n; i++) dis[i] = inf;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) ed[i][j] = inf;
}
for (int i = 0; i < m; i++) {
cin >> a[i] >> b[i];
for (int j = a[i]%b[i]; j < n; j += b[i]) ed[a[i]][j] = min(ed[a[i]][j], abs(a[i] - j) / b[i]);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (ed[i][j]) v[i].pb({j, ed[i][j]});
}
}
set <pii> s;
s.insert({0, a[0]});
dis[a[0]] = 0;
while (!s.empty()) {
auto p = s.begin();
ll x = (*p).S;
s.erase(p);
for (auto it : v[x]) {
ll y = it.F, w = it.S;
if (dis[x] + w < dis[y]) {
if (dis[y] != inf) s.erase({dis[y], y});
dis[y] = dis[x] + w;
s.insert({dis[y], y});
}
}
}
//for (int i = 0; i < n; i++) cout << dis[i] << " ";
if (dis[a[1]] != inf) cout << dis[a[1]];
else cout << -1;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
1 ms |
612 KB |
Output is correct |
10 |
Correct |
1 ms |
980 KB |
Output is correct |
11 |
Correct |
1 ms |
980 KB |
Output is correct |
12 |
Correct |
2 ms |
980 KB |
Output is correct |
13 |
Correct |
2 ms |
980 KB |
Output is correct |
14 |
Correct |
2 ms |
980 KB |
Output is correct |
15 |
Correct |
1 ms |
1000 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
1 ms |
596 KB |
Output is correct |
10 |
Correct |
1 ms |
980 KB |
Output is correct |
11 |
Correct |
1 ms |
980 KB |
Output is correct |
12 |
Correct |
2 ms |
980 KB |
Output is correct |
13 |
Correct |
2 ms |
980 KB |
Output is correct |
14 |
Correct |
1 ms |
980 KB |
Output is correct |
15 |
Correct |
2 ms |
980 KB |
Output is correct |
16 |
Correct |
2 ms |
2260 KB |
Output is correct |
17 |
Correct |
15 ms |
19232 KB |
Output is correct |
18 |
Correct |
65 ms |
82556 KB |
Output is correct |
19 |
Correct |
73 ms |
95940 KB |
Output is correct |
20 |
Correct |
102 ms |
96076 KB |
Output is correct |
21 |
Correct |
5 ms |
6268 KB |
Output is correct |
22 |
Correct |
62 ms |
85088 KB |
Output is correct |
23 |
Correct |
54 ms |
71908 KB |
Output is correct |
24 |
Correct |
72 ms |
91324 KB |
Output is correct |
25 |
Correct |
77 ms |
96020 KB |
Output is correct |
26 |
Correct |
96 ms |
95956 KB |
Output is correct |
27 |
Correct |
94 ms |
95948 KB |
Output is correct |
28 |
Correct |
90 ms |
95936 KB |
Output is correct |
29 |
Correct |
82 ms |
96004 KB |
Output is correct |
30 |
Correct |
81 ms |
95960 KB |
Output is correct |
31 |
Correct |
80 ms |
96124 KB |
Output is correct |
32 |
Correct |
95 ms |
95968 KB |
Output is correct |
33 |
Correct |
81 ms |
96044 KB |
Output is correct |
34 |
Correct |
83 ms |
96056 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
1 ms |
596 KB |
Output is correct |
10 |
Correct |
1 ms |
980 KB |
Output is correct |
11 |
Correct |
1 ms |
980 KB |
Output is correct |
12 |
Correct |
3 ms |
980 KB |
Output is correct |
13 |
Correct |
2 ms |
1004 KB |
Output is correct |
14 |
Correct |
1 ms |
980 KB |
Output is correct |
15 |
Correct |
1 ms |
980 KB |
Output is correct |
16 |
Correct |
2 ms |
2304 KB |
Output is correct |
17 |
Correct |
14 ms |
19284 KB |
Output is correct |
18 |
Correct |
60 ms |
82464 KB |
Output is correct |
19 |
Correct |
73 ms |
95856 KB |
Output is correct |
20 |
Correct |
102 ms |
96072 KB |
Output is correct |
21 |
Correct |
5 ms |
6228 KB |
Output is correct |
22 |
Correct |
62 ms |
85068 KB |
Output is correct |
23 |
Correct |
53 ms |
71836 KB |
Output is correct |
24 |
Correct |
72 ms |
91308 KB |
Output is correct |
25 |
Correct |
76 ms |
96000 KB |
Output is correct |
26 |
Correct |
96 ms |
96044 KB |
Output is correct |
27 |
Correct |
100 ms |
95944 KB |
Output is correct |
28 |
Correct |
92 ms |
96008 KB |
Output is correct |
29 |
Correct |
92 ms |
96052 KB |
Output is correct |
30 |
Correct |
81 ms |
95948 KB |
Output is correct |
31 |
Correct |
76 ms |
95964 KB |
Output is correct |
32 |
Correct |
81 ms |
95988 KB |
Output is correct |
33 |
Correct |
84 ms |
95980 KB |
Output is correct |
34 |
Correct |
84 ms |
96076 KB |
Output is correct |
35 |
Correct |
55 ms |
60960 KB |
Output is correct |
36 |
Correct |
30 ms |
37068 KB |
Output is correct |
37 |
Correct |
85 ms |
93552 KB |
Output is correct |
38 |
Correct |
90 ms |
96616 KB |
Output is correct |
39 |
Correct |
105 ms |
96760 KB |
Output is correct |
40 |
Correct |
92 ms |
96768 KB |
Output is correct |
41 |
Correct |
91 ms |
96716 KB |
Output is correct |
42 |
Correct |
414 ms |
96628 KB |
Output is correct |
43 |
Correct |
409 ms |
96616 KB |
Output is correct |
44 |
Correct |
425 ms |
96668 KB |
Output is correct |
45 |
Correct |
92 ms |
96624 KB |
Output is correct |
46 |
Correct |
92 ms |
96712 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
1 ms |
596 KB |
Output is correct |
10 |
Correct |
1 ms |
980 KB |
Output is correct |
11 |
Correct |
1 ms |
980 KB |
Output is correct |
12 |
Correct |
2 ms |
980 KB |
Output is correct |
13 |
Correct |
2 ms |
980 KB |
Output is correct |
14 |
Correct |
1 ms |
980 KB |
Output is correct |
15 |
Correct |
1 ms |
980 KB |
Output is correct |
16 |
Correct |
2 ms |
2284 KB |
Output is correct |
17 |
Correct |
17 ms |
19284 KB |
Output is correct |
18 |
Correct |
60 ms |
82508 KB |
Output is correct |
19 |
Correct |
77 ms |
95944 KB |
Output is correct |
20 |
Correct |
103 ms |
96076 KB |
Output is correct |
21 |
Correct |
5 ms |
6228 KB |
Output is correct |
22 |
Correct |
63 ms |
85124 KB |
Output is correct |
23 |
Correct |
57 ms |
71912 KB |
Output is correct |
24 |
Correct |
71 ms |
91320 KB |
Output is correct |
25 |
Correct |
78 ms |
96076 KB |
Output is correct |
26 |
Correct |
97 ms |
95924 KB |
Output is correct |
27 |
Correct |
97 ms |
96048 KB |
Output is correct |
28 |
Correct |
82 ms |
95948 KB |
Output is correct |
29 |
Correct |
91 ms |
96032 KB |
Output is correct |
30 |
Correct |
81 ms |
95948 KB |
Output is correct |
31 |
Correct |
87 ms |
96036 KB |
Output is correct |
32 |
Correct |
92 ms |
95952 KB |
Output is correct |
33 |
Correct |
87 ms |
95976 KB |
Output is correct |
34 |
Correct |
82 ms |
95980 KB |
Output is correct |
35 |
Correct |
55 ms |
60928 KB |
Output is correct |
36 |
Correct |
31 ms |
37016 KB |
Output is correct |
37 |
Correct |
83 ms |
93440 KB |
Output is correct |
38 |
Correct |
92 ms |
96600 KB |
Output is correct |
39 |
Correct |
91 ms |
96716 KB |
Output is correct |
40 |
Correct |
92 ms |
96700 KB |
Output is correct |
41 |
Correct |
91 ms |
96676 KB |
Output is correct |
42 |
Correct |
414 ms |
96608 KB |
Output is correct |
43 |
Correct |
409 ms |
96616 KB |
Output is correct |
44 |
Correct |
426 ms |
96736 KB |
Output is correct |
45 |
Correct |
91 ms |
96620 KB |
Output is correct |
46 |
Correct |
92 ms |
96684 KB |
Output is correct |
47 |
Runtime error |
47 ms |
65864 KB |
Execution killed with signal 11 |
48 |
Halted |
0 ms |
0 KB |
- |