#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i<= b; ++i)
#define FORD(i, a, b) for (int i = a; i>=b; --i)
#define REP(i, a) for (int i = 0; i<a; ++i)
#define DEBUG(x) { cerr << #x << " = " << x << endl; }
#define Arr(A, l, r) { cerr << #A << " = "; FOR(_, l, r) cerr << A[_] << ' '; cerr << endl; }
#define N 1001000
#define pp pair<int, int>
#define next __next
#define prev __prev
#define __builtin_popcount __builtin_popcountll
#define bit(S, i) (((S) >> i) & 1)
#define IO ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define all(s) s.begin(), s.end()
using namespace std;
int n, m;
vector<pp> e[N];
priority_queue<pp> heap;
int d[N];
int fUnion[N], p[N];
vector<int> Query[N];
int l[N], r[N], s[N], t[N], cur[N];
bool mark[N];
void Union(int a, int b) {
int t = fUnion[a] + fUnion[b];
if (fUnion[a] > fUnion[b]) swap(a, b);
fUnion[a] = t;
fUnion[b] = a;
}
int root(int u) { return fUnion[u] < 0 ? u : (fUnion[u] = root(fUnion[u])); }
int main() {
IO;
cin >> n >> m;
REP(i, m) {
int u, v, c;
cin >> u >> v >> c;
e[u].push_back(pp(v, c));
e[v].push_back(pp(u, c));
}
int k;
cin >> k;
FOR(i, 1, n) d[i] = 1e9;
REP(i, k) {
int x;
cin >> x;
heap.push(pp(d[x] = 0, x));
}
while (!heap.empty()) {
int u = heap.top().second;
int dis = -heap.top().first;
heap.pop();
if (dis != d[u]) continue;
for (pp t : e[u]) {
int newD = d[u] + t.second;
int v = t.first;
if (d[v] > newD) heap.push(pp(-(d[v] = newD), v));
}
}
FOR(i, 1, n) p[i] = i;
sort(p + 1, p + n + 1, [] (const int &a, const int &b) {
return d[a] > d[b];
});
//Read query
int q;
cin >> q;
FOR(i, 1, q) cin >> s[i] >> t[i];
//Parallel Binary Search
FOR(i, 1, q) l[i] = 1, r[i] = n;
bool changed = true;
while (changed) {
changed = false;
FOR(i, 1, n) {
Query[i].clear();
fUnion[i] = -1;
mark[i] = false;
}
FOR(i, 1, q) if (l[i] <= r[i]) {
Query[(l[i] + r[i]) >> 1].push_back(i);
changed = true;
}
FOR(i, 1, n) {
int u = p[i];
mark[u] = true;
for (pp t : e[u]) {
int v = t.first;
if (mark[v]) {
int a = root(u);
int b = root(v);
if (a != b) Union(a, b);
}
}
for (int x : Query[i]) {
if (root(s[x]) == root(t[x])) cur[x] = i, r[x] = i - 1;
else l[x] = i + 1;
}
}
}
FOR(i, 1, q) cout << d[p[cur[i]]] << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
45 ms |
47432 KB |
Output is correct |
2 |
Correct |
46 ms |
47612 KB |
Output is correct |
3 |
Correct |
48 ms |
47672 KB |
Output is correct |
4 |
Correct |
52 ms |
47352 KB |
Output is correct |
5 |
Correct |
46 ms |
47604 KB |
Output is correct |
6 |
Correct |
57 ms |
47588 KB |
Output is correct |
7 |
Correct |
44 ms |
47352 KB |
Output is correct |
8 |
Correct |
45 ms |
47352 KB |
Output is correct |
9 |
Correct |
46 ms |
47608 KB |
Output is correct |
10 |
Correct |
46 ms |
47608 KB |
Output is correct |
11 |
Correct |
47 ms |
47628 KB |
Output is correct |
12 |
Correct |
46 ms |
47480 KB |
Output is correct |
13 |
Correct |
46 ms |
47608 KB |
Output is correct |
14 |
Correct |
46 ms |
47516 KB |
Output is correct |
15 |
Correct |
47 ms |
47592 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
45 ms |
47432 KB |
Output is correct |
2 |
Correct |
46 ms |
47612 KB |
Output is correct |
3 |
Correct |
48 ms |
47672 KB |
Output is correct |
4 |
Correct |
52 ms |
47352 KB |
Output is correct |
5 |
Correct |
46 ms |
47604 KB |
Output is correct |
6 |
Correct |
57 ms |
47588 KB |
Output is correct |
7 |
Correct |
44 ms |
47352 KB |
Output is correct |
8 |
Correct |
45 ms |
47352 KB |
Output is correct |
9 |
Correct |
46 ms |
47608 KB |
Output is correct |
10 |
Correct |
46 ms |
47608 KB |
Output is correct |
11 |
Correct |
47 ms |
47628 KB |
Output is correct |
12 |
Correct |
46 ms |
47480 KB |
Output is correct |
13 |
Correct |
46 ms |
47608 KB |
Output is correct |
14 |
Correct |
46 ms |
47516 KB |
Output is correct |
15 |
Correct |
47 ms |
47592 KB |
Output is correct |
16 |
Correct |
460 ms |
64436 KB |
Output is correct |
17 |
Correct |
1222 ms |
75272 KB |
Output is correct |
18 |
Correct |
102 ms |
50168 KB |
Output is correct |
19 |
Correct |
241 ms |
63440 KB |
Output is correct |
20 |
Correct |
1181 ms |
75268 KB |
Output is correct |
21 |
Correct |
663 ms |
68124 KB |
Output is correct |
22 |
Correct |
476 ms |
65028 KB |
Output is correct |
23 |
Correct |
1176 ms |
75504 KB |
Output is correct |
24 |
Correct |
1187 ms |
75640 KB |
Output is correct |
25 |
Correct |
1213 ms |
75448 KB |
Output is correct |
26 |
Correct |
249 ms |
63336 KB |
Output is correct |
27 |
Correct |
254 ms |
63848 KB |
Output is correct |
28 |
Correct |
296 ms |
63920 KB |
Output is correct |
29 |
Correct |
252 ms |
63436 KB |
Output is correct |
30 |
Correct |
237 ms |
63692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
46 ms |
47420 KB |
Output is correct |
2 |
Correct |
46 ms |
47352 KB |
Output is correct |
3 |
Correct |
46 ms |
47352 KB |
Output is correct |
4 |
Correct |
46 ms |
47476 KB |
Output is correct |
5 |
Correct |
46 ms |
47352 KB |
Output is correct |
6 |
Correct |
45 ms |
47476 KB |
Output is correct |
7 |
Correct |
45 ms |
47352 KB |
Output is correct |
8 |
Correct |
45 ms |
47352 KB |
Output is correct |
9 |
Correct |
45 ms |
47352 KB |
Output is correct |
10 |
Correct |
45 ms |
47352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
536 ms |
55792 KB |
Output is correct |
2 |
Correct |
978 ms |
64600 KB |
Output is correct |
3 |
Correct |
917 ms |
64560 KB |
Output is correct |
4 |
Correct |
240 ms |
52244 KB |
Output is correct |
5 |
Correct |
959 ms |
64664 KB |
Output is correct |
6 |
Correct |
965 ms |
64764 KB |
Output is correct |
7 |
Correct |
978 ms |
64700 KB |
Output is correct |
8 |
Correct |
945 ms |
64676 KB |
Output is correct |
9 |
Correct |
990 ms |
64496 KB |
Output is correct |
10 |
Correct |
959 ms |
64004 KB |
Output is correct |
11 |
Correct |
937 ms |
64112 KB |
Output is correct |
12 |
Correct |
899 ms |
64076 KB |
Output is correct |
13 |
Correct |
960 ms |
64100 KB |
Output is correct |
14 |
Correct |
952 ms |
63852 KB |
Output is correct |
15 |
Correct |
1006 ms |
63960 KB |
Output is correct |
16 |
Correct |
959 ms |
63892 KB |
Output is correct |
17 |
Correct |
945 ms |
63876 KB |
Output is correct |
18 |
Correct |
1018 ms |
63852 KB |
Output is correct |
19 |
Correct |
219 ms |
51872 KB |
Output is correct |
20 |
Correct |
988 ms |
63820 KB |
Output is correct |
21 |
Correct |
822 ms |
63548 KB |
Output is correct |
22 |
Correct |
165 ms |
53616 KB |
Output is correct |
23 |
Correct |
230 ms |
52344 KB |
Output is correct |
24 |
Correct |
179 ms |
53480 KB |
Output is correct |
25 |
Correct |
167 ms |
53588 KB |
Output is correct |
26 |
Correct |
251 ms |
52544 KB |
Output is correct |
27 |
Correct |
225 ms |
51856 KB |
Output is correct |
28 |
Correct |
166 ms |
53484 KB |
Output is correct |
29 |
Correct |
224 ms |
51960 KB |
Output is correct |
30 |
Correct |
166 ms |
53552 KB |
Output is correct |
31 |
Correct |
279 ms |
51836 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
45 ms |
47432 KB |
Output is correct |
2 |
Correct |
46 ms |
47612 KB |
Output is correct |
3 |
Correct |
48 ms |
47672 KB |
Output is correct |
4 |
Correct |
52 ms |
47352 KB |
Output is correct |
5 |
Correct |
46 ms |
47604 KB |
Output is correct |
6 |
Correct |
57 ms |
47588 KB |
Output is correct |
7 |
Correct |
44 ms |
47352 KB |
Output is correct |
8 |
Correct |
45 ms |
47352 KB |
Output is correct |
9 |
Correct |
46 ms |
47608 KB |
Output is correct |
10 |
Correct |
46 ms |
47608 KB |
Output is correct |
11 |
Correct |
47 ms |
47628 KB |
Output is correct |
12 |
Correct |
46 ms |
47480 KB |
Output is correct |
13 |
Correct |
46 ms |
47608 KB |
Output is correct |
14 |
Correct |
46 ms |
47516 KB |
Output is correct |
15 |
Correct |
47 ms |
47592 KB |
Output is correct |
16 |
Correct |
460 ms |
64436 KB |
Output is correct |
17 |
Correct |
1222 ms |
75272 KB |
Output is correct |
18 |
Correct |
102 ms |
50168 KB |
Output is correct |
19 |
Correct |
241 ms |
63440 KB |
Output is correct |
20 |
Correct |
1181 ms |
75268 KB |
Output is correct |
21 |
Correct |
663 ms |
68124 KB |
Output is correct |
22 |
Correct |
476 ms |
65028 KB |
Output is correct |
23 |
Correct |
1176 ms |
75504 KB |
Output is correct |
24 |
Correct |
1187 ms |
75640 KB |
Output is correct |
25 |
Correct |
1213 ms |
75448 KB |
Output is correct |
26 |
Correct |
249 ms |
63336 KB |
Output is correct |
27 |
Correct |
254 ms |
63848 KB |
Output is correct |
28 |
Correct |
296 ms |
63920 KB |
Output is correct |
29 |
Correct |
252 ms |
63436 KB |
Output is correct |
30 |
Correct |
237 ms |
63692 KB |
Output is correct |
31 |
Correct |
46 ms |
47420 KB |
Output is correct |
32 |
Correct |
46 ms |
47352 KB |
Output is correct |
33 |
Correct |
46 ms |
47352 KB |
Output is correct |
34 |
Correct |
46 ms |
47476 KB |
Output is correct |
35 |
Correct |
46 ms |
47352 KB |
Output is correct |
36 |
Correct |
45 ms |
47476 KB |
Output is correct |
37 |
Correct |
45 ms |
47352 KB |
Output is correct |
38 |
Correct |
45 ms |
47352 KB |
Output is correct |
39 |
Correct |
45 ms |
47352 KB |
Output is correct |
40 |
Correct |
45 ms |
47352 KB |
Output is correct |
41 |
Correct |
536 ms |
55792 KB |
Output is correct |
42 |
Correct |
978 ms |
64600 KB |
Output is correct |
43 |
Correct |
917 ms |
64560 KB |
Output is correct |
44 |
Correct |
240 ms |
52244 KB |
Output is correct |
45 |
Correct |
959 ms |
64664 KB |
Output is correct |
46 |
Correct |
965 ms |
64764 KB |
Output is correct |
47 |
Correct |
978 ms |
64700 KB |
Output is correct |
48 |
Correct |
945 ms |
64676 KB |
Output is correct |
49 |
Correct |
990 ms |
64496 KB |
Output is correct |
50 |
Correct |
959 ms |
64004 KB |
Output is correct |
51 |
Correct |
937 ms |
64112 KB |
Output is correct |
52 |
Correct |
899 ms |
64076 KB |
Output is correct |
53 |
Correct |
960 ms |
64100 KB |
Output is correct |
54 |
Correct |
952 ms |
63852 KB |
Output is correct |
55 |
Correct |
1006 ms |
63960 KB |
Output is correct |
56 |
Correct |
959 ms |
63892 KB |
Output is correct |
57 |
Correct |
945 ms |
63876 KB |
Output is correct |
58 |
Correct |
1018 ms |
63852 KB |
Output is correct |
59 |
Correct |
219 ms |
51872 KB |
Output is correct |
60 |
Correct |
988 ms |
63820 KB |
Output is correct |
61 |
Correct |
822 ms |
63548 KB |
Output is correct |
62 |
Correct |
165 ms |
53616 KB |
Output is correct |
63 |
Correct |
230 ms |
52344 KB |
Output is correct |
64 |
Correct |
179 ms |
53480 KB |
Output is correct |
65 |
Correct |
167 ms |
53588 KB |
Output is correct |
66 |
Correct |
251 ms |
52544 KB |
Output is correct |
67 |
Correct |
225 ms |
51856 KB |
Output is correct |
68 |
Correct |
166 ms |
53484 KB |
Output is correct |
69 |
Correct |
224 ms |
51960 KB |
Output is correct |
70 |
Correct |
166 ms |
53552 KB |
Output is correct |
71 |
Correct |
279 ms |
51836 KB |
Output is correct |
72 |
Correct |
735 ms |
67312 KB |
Output is correct |
73 |
Correct |
1157 ms |
74788 KB |
Output is correct |
74 |
Correct |
1163 ms |
74664 KB |
Output is correct |
75 |
Correct |
1156 ms |
76072 KB |
Output is correct |
76 |
Correct |
1200 ms |
75932 KB |
Output is correct |
77 |
Correct |
1184 ms |
75840 KB |
Output is correct |
78 |
Correct |
1143 ms |
76008 KB |
Output is correct |
79 |
Correct |
1235 ms |
76076 KB |
Output is correct |
80 |
Correct |
1176 ms |
75256 KB |
Output is correct |
81 |
Correct |
1150 ms |
75836 KB |
Output is correct |
82 |
Correct |
1168 ms |
75360 KB |
Output is correct |
83 |
Correct |
1178 ms |
75092 KB |
Output is correct |
84 |
Correct |
1180 ms |
75668 KB |
Output is correct |
85 |
Correct |
1201 ms |
75508 KB |
Output is correct |
86 |
Correct |
1205 ms |
75500 KB |
Output is correct |
87 |
Correct |
1267 ms |
75924 KB |
Output is correct |
88 |
Correct |
1195 ms |
75784 KB |
Output is correct |
89 |
Correct |
475 ms |
65816 KB |
Output is correct |
90 |
Correct |
1200 ms |
75952 KB |
Output is correct |
91 |
Correct |
1063 ms |
75268 KB |
Output is correct |
92 |
Correct |
251 ms |
64360 KB |
Output is correct |
93 |
Correct |
472 ms |
64588 KB |
Output is correct |
94 |
Correct |
254 ms |
64248 KB |
Output is correct |
95 |
Correct |
234 ms |
63804 KB |
Output is correct |
96 |
Correct |
396 ms |
63028 KB |
Output is correct |
97 |
Correct |
462 ms |
64928 KB |
Output is correct |
98 |
Correct |
251 ms |
63416 KB |
Output is correct |
99 |
Correct |
461 ms |
64424 KB |
Output is correct |
100 |
Correct |
254 ms |
64316 KB |
Output is correct |