#include <bits/stdc++.h>
using namespace std;
#define int long long
#define tp3 tuple<int, int, int>
#define all(x) x.begin(), x.end()
const int N = 5e3+3, M = 32, inf = 1e18;
int n, e, k, q, a[N], dis[M][M][N];
vector<pair<int, int>> adj[N];
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
for (int i = 0; i < M; i++) {
for (int j = 0; j < M; j++) {
for (int ij = 0; ij < N; ij++) {
dis[i][j][ij] = inf;
}
}
}
cin >> n >> e >> k;
for (int i = 0; i < k; i++) {
int x;
cin >> x;
a[i] = x;
}
for (int i = 0; i < e; i++) {
int x, y, z;
cin >> x >> y >> z;
adj[y].push_back(make_pair(x, z));
}
for (int mask = 0; mask < M; mask++) {
priority_queue<tp3> pq;
for (int i = 0; i < k; i++) {
pq.push(make_tuple(-0, mask, a[i]));
}
while (!pq.empty()) {
int d = -get<0>(pq.top());
int nwMask = get<1>(pq.top());
int x = get<2>(pq.top());
pq.pop();
if (dis[mask][nwMask][x] <= d) continue;
dis[mask][nwMask][x] = d;//cerr << x << " " << d << " " << nwMask << " " << mask << endl;
for (auto& [y, z] : adj[x]) {
for (int i = 0; i < 5; i++) {
// uso el ticket i
if (!((nwMask >> i) & 1) || dis[mask][nwMask][y] <= d + z * (10-i-1)/10) continue;
pq.push(make_tuple(-(d + (z*(10-i-1)) / 10), nwMask ^ (1 << i), y));
}
if (dis[mask][nwMask][y] <= d+z) continue;
pq.push(make_tuple(-(d+z), nwMask, y));
}
}
}
cin >> q;
while (q--) {
int s, p[5];
cin >> s;
for (int i = 0; i < 5; i++) {
cin >> p[i];
}
int ans = inf;
for (int mask = 0; mask < M; mask++) {
int sum = 0;
bool ok = 1;
for (int i = 0; i < 5; i++) {
if ((mask >> i) & 1) {
if (p[i] == -1) ok = 0;
sum += p[i];
}
}
//if (dis[mask][0][s] < inf && ok) cerr << sum << " " << mask << " " << dis[mask][0][s] << " " << dis[mask][0][s] + sum << endl;
if (ok) ans = min(ans, dis[mask][0][s] + sum);
}
cout << (ans == inf ? -1 : ans) << "\n";
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
441 ms |
46460 KB |
Output is correct |
2 |
Correct |
182 ms |
40908 KB |
Output is correct |
3 |
Correct |
499 ms |
46732 KB |
Output is correct |
4 |
Correct |
7 ms |
40536 KB |
Output is correct |
5 |
Correct |
7 ms |
40540 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
441 ms |
46460 KB |
Output is correct |
2 |
Correct |
182 ms |
40908 KB |
Output is correct |
3 |
Correct |
499 ms |
46732 KB |
Output is correct |
4 |
Correct |
7 ms |
40536 KB |
Output is correct |
5 |
Correct |
7 ms |
40540 KB |
Output is correct |
6 |
Correct |
465 ms |
46908 KB |
Output is correct |
7 |
Correct |
177 ms |
40796 KB |
Output is correct |
8 |
Correct |
501 ms |
45732 KB |
Output is correct |
9 |
Correct |
7 ms |
40540 KB |
Output is correct |
10 |
Correct |
7 ms |
40612 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
441 ms |
46460 KB |
Output is correct |
2 |
Correct |
182 ms |
40908 KB |
Output is correct |
3 |
Correct |
499 ms |
46732 KB |
Output is correct |
4 |
Correct |
7 ms |
40536 KB |
Output is correct |
5 |
Correct |
7 ms |
40540 KB |
Output is correct |
6 |
Correct |
465 ms |
46908 KB |
Output is correct |
7 |
Correct |
177 ms |
40796 KB |
Output is correct |
8 |
Correct |
501 ms |
45732 KB |
Output is correct |
9 |
Correct |
7 ms |
40540 KB |
Output is correct |
10 |
Correct |
7 ms |
40612 KB |
Output is correct |
11 |
Correct |
489 ms |
51788 KB |
Output is correct |
12 |
Correct |
218 ms |
40936 KB |
Output is correct |
13 |
Correct |
498 ms |
46364 KB |
Output is correct |
14 |
Correct |
7 ms |
40600 KB |
Output is correct |
15 |
Correct |
7 ms |
40608 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
441 ms |
46460 KB |
Output is correct |
2 |
Correct |
182 ms |
40908 KB |
Output is correct |
3 |
Correct |
499 ms |
46732 KB |
Output is correct |
4 |
Correct |
7 ms |
40536 KB |
Output is correct |
5 |
Correct |
7 ms |
40540 KB |
Output is correct |
6 |
Correct |
9 ms |
41048 KB |
Output is correct |
7 |
Correct |
180 ms |
40920 KB |
Output is correct |
8 |
Correct |
506 ms |
46608 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
441 ms |
46460 KB |
Output is correct |
2 |
Correct |
182 ms |
40908 KB |
Output is correct |
3 |
Correct |
499 ms |
46732 KB |
Output is correct |
4 |
Correct |
7 ms |
40536 KB |
Output is correct |
5 |
Correct |
7 ms |
40540 KB |
Output is correct |
6 |
Correct |
465 ms |
46908 KB |
Output is correct |
7 |
Correct |
177 ms |
40796 KB |
Output is correct |
8 |
Correct |
501 ms |
45732 KB |
Output is correct |
9 |
Correct |
7 ms |
40540 KB |
Output is correct |
10 |
Correct |
7 ms |
40612 KB |
Output is correct |
11 |
Correct |
9 ms |
41048 KB |
Output is correct |
12 |
Correct |
180 ms |
40920 KB |
Output is correct |
13 |
Correct |
506 ms |
46608 KB |
Output is correct |
14 |
Correct |
465 ms |
46692 KB |
Output is correct |
15 |
Correct |
175 ms |
40924 KB |
Output is correct |
16 |
Correct |
504 ms |
46428 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
463 ms |
48084 KB |
Output is correct |
2 |
Correct |
469 ms |
51576 KB |
Output is correct |
3 |
Correct |
335 ms |
41300 KB |
Output is correct |
4 |
Correct |
507 ms |
45648 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
50 ms |
42888 KB |
Output is correct |
2 |
Correct |
49 ms |
43044 KB |
Output is correct |
3 |
Correct |
12 ms |
41052 KB |
Output is correct |
4 |
Correct |
40 ms |
42344 KB |
Output is correct |
5 |
Correct |
47 ms |
42864 KB |
Output is correct |
6 |
Correct |
11 ms |
40536 KB |
Output is correct |
7 |
Correct |
48 ms |
43032 KB |
Output is correct |
8 |
Correct |
49 ms |
43044 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
441 ms |
46460 KB |
Output is correct |
2 |
Correct |
182 ms |
40908 KB |
Output is correct |
3 |
Correct |
499 ms |
46732 KB |
Output is correct |
4 |
Correct |
7 ms |
40536 KB |
Output is correct |
5 |
Correct |
7 ms |
40540 KB |
Output is correct |
6 |
Correct |
465 ms |
46908 KB |
Output is correct |
7 |
Correct |
177 ms |
40796 KB |
Output is correct |
8 |
Correct |
501 ms |
45732 KB |
Output is correct |
9 |
Correct |
7 ms |
40540 KB |
Output is correct |
10 |
Correct |
7 ms |
40612 KB |
Output is correct |
11 |
Correct |
489 ms |
51788 KB |
Output is correct |
12 |
Correct |
218 ms |
40936 KB |
Output is correct |
13 |
Correct |
498 ms |
46364 KB |
Output is correct |
14 |
Correct |
7 ms |
40600 KB |
Output is correct |
15 |
Correct |
7 ms |
40608 KB |
Output is correct |
16 |
Correct |
9 ms |
41048 KB |
Output is correct |
17 |
Correct |
180 ms |
40920 KB |
Output is correct |
18 |
Correct |
506 ms |
46608 KB |
Output is correct |
19 |
Correct |
465 ms |
46692 KB |
Output is correct |
20 |
Correct |
175 ms |
40924 KB |
Output is correct |
21 |
Correct |
504 ms |
46428 KB |
Output is correct |
22 |
Correct |
463 ms |
48084 KB |
Output is correct |
23 |
Correct |
469 ms |
51576 KB |
Output is correct |
24 |
Correct |
335 ms |
41300 KB |
Output is correct |
25 |
Correct |
507 ms |
45648 KB |
Output is correct |
26 |
Correct |
50 ms |
42888 KB |
Output is correct |
27 |
Correct |
49 ms |
43044 KB |
Output is correct |
28 |
Correct |
12 ms |
41052 KB |
Output is correct |
29 |
Correct |
40 ms |
42344 KB |
Output is correct |
30 |
Correct |
47 ms |
42864 KB |
Output is correct |
31 |
Correct |
11 ms |
40536 KB |
Output is correct |
32 |
Correct |
48 ms |
43032 KB |
Output is correct |
33 |
Correct |
49 ms |
43044 KB |
Output is correct |
34 |
Correct |
7 ms |
40536 KB |
Output is correct |
35 |
Correct |
7 ms |
40540 KB |
Output is correct |
36 |
Correct |
7 ms |
40608 KB |
Output is correct |
37 |
Correct |
481 ms |
52196 KB |
Output is correct |
38 |
Correct |
493 ms |
51456 KB |
Output is correct |
39 |
Correct |
488 ms |
45564 KB |
Output is correct |
40 |
Correct |
8 ms |
40540 KB |
Output is correct |
41 |
Correct |
27 ms |
41052 KB |
Output is correct |
42 |
Correct |
553 ms |
50572 KB |
Output is correct |
43 |
Correct |
580 ms |
50348 KB |
Output is correct |
44 |
Correct |
530 ms |
45776 KB |
Output is correct |
45 |
Correct |
346 ms |
41236 KB |
Output is correct |