/**
* code generated by JHelper
* More info: https://github.com/AlexeyDmitriev/JHelper
* @author Miguel Mini
*/
#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define trav(v, x) for (auto v : x)
#define re(x, y, z) for (int x=y; x<z; ++x)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define set_to(x, v) fill(all(x), v)
#define eb emplace_back
#define lso(x) ((x)&-(x))
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;
const int inf = 1e9 + 10;
vector<ii> g[maxn];
int c[maxn];
int dis[maxn];
int n, k;
void dijkstra() {
fill(dis+1, dis+n+1, inf);
priority_queue<ii, vector<ii>, greater<ii>> Q;
re(i, 0, k) {
Q.push({dis[c[i]] = 0, c[i]});
}
while (!Q.empty()) {
auto q = Q.top(); Q.pop();
int w = q.first;
int v = q.second;
if (w != dis[v]) continue;
for (auto node : g[v]) {
int temp = w + node.second;
int u = node.first;
if (temp < dis[u]) {
dis[u] = temp;
Q.push({dis[u], u});
}
}
}
}
int rnk[maxn], link[maxn];
void make(int x) {
link[x] = x;
rnk[x] = 0;
}
int get(int x) {
if (x == link[x]) return x;
return link[x] = get(link[x]);
}
bool merge(int x, int y) {
x = get(x); y = get(y);
if (x == y) return 0;
if (rnk[x] < rnk[y]) swap(x, y);
rnk[x] += rnk[x] == rnk[y];
link[y] = x;
}
vector<ii> T[maxn];
int h[maxn];
const int LOG = 18;
int st[maxn][LOG];
int min_edge[maxn][LOG];
void dfs(int x, int p=0, int e=0) {
h[x] = p == 0 ? 0 : h[p] + 1;
st[x][0] = p == 0 ? x : p;
min_edge[x][0] = e;
for (int k = 1; k < LOG; ++k) {
st[x][k] = st[st[x][k-1]][k-1];
min_edge[x][k] = min(min_edge[x][k-1], min_edge[st[x][k-1]][k-1]);
}
for (auto e : T[x]) {
if (e.first == p) continue;
dfs(e.first, x, e.second);
}
}
int jump(int x, int l) {
for (int k = 0; k < LOG; ++k) {
if (l & (1<<k)) {
x = st[x][k];
}
}
return x;
}
int lca(int x, int y) {
if (h[x] > h[y]) swap(x, y);
y = jump(y, h[y] - h[x]);
if (x == y) return x;
for (int k = LOG-1; k >= 0; --k) {
if (st[x][k] != st[y][k]) {
x = st[x][k];
y = st[y][k];
}
}
return st[x][0];
}
int min_edge_jump(int x, int l) {
int ans = inf;
for (int k = LOG-1; k >= 0; --k) {
if (l & (1<<k)) {
ans = min(ans, min_edge[x][k]);
x = st[x][k];
}
}
return ans;
}
int get_min(int a, int b) {
int c = lca(a, b);
return min(min_edge_jump(a, h[a]-h[c]), min_edge_jump(b, h[b]-h[c]));
}
class IZHO_18_plan {
public:
void solveOne(istream& in, ostream& out) {
int m;
in >> n >> m;
vector<pair<ii, int>> edges;
re(i, 0, m) {
int a, b, w;
in >> a >> b >> w;
g[a].eb(b, w);
g[b].eb(a, w);
edges.push_back({{a, b}, 0});
}
in >> k;
re(i, 0, k) in >> c[i];
dijkstra();
for (auto& e : edges) {
e.second = min(dis[e.first.first], dis[e.first.second]);
}
sort(all(edges), [](pair<ii, int> p, pair<ii, int> q) {
return p.second > q.second;
});
re(i, 1, n+1) make(i);
for (auto e : edges) {
if (merge(e.first.first, e.first.second)) {
T[e.first.first].push_back({e.first.second, e.second});
T[e.first.second].push_back({e.first.first, e.second});
}
}
dfs(1);
int q;
in >> q;
while (q--) {
int a, b;
in >> a >> b;
out << get_min(a, b) << endl;
}
}
void solve(istream& in, ostream& out) {
int testNumber = 1;
//in >> testNumber;
re(tc, 1, testNumber+1) {
//out << "Case #" << tc << ": ";
solveOne(in, out);
}
}
};
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
IZHO_18_plan solver;
std::istream& in(std::cin);
std::ostream& out(std::cout);
solver.solve(in, out);
return 0;
}
Compilation message
plan.cpp: In function 'bool merge(int, int)':
plan.cpp:67:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5120 KB |
Output is correct |
2 |
Correct |
10 ms |
5376 KB |
Output is correct |
3 |
Correct |
10 ms |
5376 KB |
Output is correct |
4 |
Correct |
7 ms |
5120 KB |
Output is correct |
5 |
Correct |
11 ms |
5376 KB |
Output is correct |
6 |
Correct |
11 ms |
5376 KB |
Output is correct |
7 |
Correct |
8 ms |
5120 KB |
Output is correct |
8 |
Correct |
7 ms |
5120 KB |
Output is correct |
9 |
Correct |
10 ms |
5376 KB |
Output is correct |
10 |
Correct |
10 ms |
5376 KB |
Output is correct |
11 |
Correct |
10 ms |
5376 KB |
Output is correct |
12 |
Correct |
12 ms |
5376 KB |
Output is correct |
13 |
Correct |
10 ms |
5376 KB |
Output is correct |
14 |
Correct |
11 ms |
5376 KB |
Output is correct |
15 |
Correct |
10 ms |
5376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5120 KB |
Output is correct |
2 |
Correct |
10 ms |
5376 KB |
Output is correct |
3 |
Correct |
10 ms |
5376 KB |
Output is correct |
4 |
Correct |
7 ms |
5120 KB |
Output is correct |
5 |
Correct |
11 ms |
5376 KB |
Output is correct |
6 |
Correct |
11 ms |
5376 KB |
Output is correct |
7 |
Correct |
8 ms |
5120 KB |
Output is correct |
8 |
Correct |
7 ms |
5120 KB |
Output is correct |
9 |
Correct |
10 ms |
5376 KB |
Output is correct |
10 |
Correct |
10 ms |
5376 KB |
Output is correct |
11 |
Correct |
10 ms |
5376 KB |
Output is correct |
12 |
Correct |
12 ms |
5376 KB |
Output is correct |
13 |
Correct |
10 ms |
5376 KB |
Output is correct |
14 |
Correct |
11 ms |
5376 KB |
Output is correct |
15 |
Correct |
10 ms |
5376 KB |
Output is correct |
16 |
Correct |
382 ms |
27816 KB |
Output is correct |
17 |
Correct |
800 ms |
49688 KB |
Output is correct |
18 |
Correct |
62 ms |
9904 KB |
Output is correct |
19 |
Correct |
364 ms |
33088 KB |
Output is correct |
20 |
Correct |
789 ms |
49816 KB |
Output is correct |
21 |
Correct |
511 ms |
37744 KB |
Output is correct |
22 |
Correct |
394 ms |
36504 KB |
Output is correct |
23 |
Correct |
816 ms |
49624 KB |
Output is correct |
24 |
Correct |
766 ms |
49688 KB |
Output is correct |
25 |
Correct |
763 ms |
49812 KB |
Output is correct |
26 |
Correct |
355 ms |
32912 KB |
Output is correct |
27 |
Correct |
365 ms |
33032 KB |
Output is correct |
28 |
Correct |
386 ms |
32780 KB |
Output is correct |
29 |
Correct |
359 ms |
33036 KB |
Output is correct |
30 |
Correct |
376 ms |
33168 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
5120 KB |
Output is correct |
2 |
Correct |
7 ms |
5120 KB |
Output is correct |
3 |
Correct |
8 ms |
5120 KB |
Output is correct |
4 |
Correct |
7 ms |
5120 KB |
Output is correct |
5 |
Correct |
8 ms |
5120 KB |
Output is correct |
6 |
Correct |
8 ms |
5120 KB |
Output is correct |
7 |
Correct |
7 ms |
5120 KB |
Output is correct |
8 |
Correct |
7 ms |
5120 KB |
Output is correct |
9 |
Correct |
9 ms |
5120 KB |
Output is correct |
10 |
Correct |
8 ms |
5120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
284 ms |
35756 KB |
Output is correct |
2 |
Correct |
524 ms |
49360 KB |
Output is correct |
3 |
Correct |
494 ms |
49368 KB |
Output is correct |
4 |
Correct |
158 ms |
32680 KB |
Output is correct |
5 |
Correct |
517 ms |
49304 KB |
Output is correct |
6 |
Correct |
520 ms |
49432 KB |
Output is correct |
7 |
Correct |
514 ms |
49304 KB |
Output is correct |
8 |
Correct |
495 ms |
49276 KB |
Output is correct |
9 |
Correct |
496 ms |
49304 KB |
Output is correct |
10 |
Correct |
490 ms |
49348 KB |
Output is correct |
11 |
Correct |
495 ms |
49400 KB |
Output is correct |
12 |
Correct |
504 ms |
49292 KB |
Output is correct |
13 |
Correct |
503 ms |
49432 KB |
Output is correct |
14 |
Correct |
530 ms |
49584 KB |
Output is correct |
15 |
Correct |
517 ms |
50460 KB |
Output is correct |
16 |
Correct |
554 ms |
49512 KB |
Output is correct |
17 |
Correct |
518 ms |
49432 KB |
Output is correct |
18 |
Correct |
505 ms |
49432 KB |
Output is correct |
19 |
Correct |
140 ms |
34220 KB |
Output is correct |
20 |
Correct |
536 ms |
49436 KB |
Output is correct |
21 |
Correct |
470 ms |
49688 KB |
Output is correct |
22 |
Correct |
133 ms |
31368 KB |
Output is correct |
23 |
Correct |
149 ms |
31376 KB |
Output is correct |
24 |
Correct |
125 ms |
31376 KB |
Output is correct |
25 |
Correct |
130 ms |
31496 KB |
Output is correct |
26 |
Correct |
163 ms |
31532 KB |
Output is correct |
27 |
Correct |
169 ms |
34088 KB |
Output is correct |
28 |
Correct |
127 ms |
31380 KB |
Output is correct |
29 |
Correct |
155 ms |
33324 KB |
Output is correct |
30 |
Correct |
124 ms |
31372 KB |
Output is correct |
31 |
Correct |
152 ms |
33320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5120 KB |
Output is correct |
2 |
Correct |
10 ms |
5376 KB |
Output is correct |
3 |
Correct |
10 ms |
5376 KB |
Output is correct |
4 |
Correct |
7 ms |
5120 KB |
Output is correct |
5 |
Correct |
11 ms |
5376 KB |
Output is correct |
6 |
Correct |
11 ms |
5376 KB |
Output is correct |
7 |
Correct |
8 ms |
5120 KB |
Output is correct |
8 |
Correct |
7 ms |
5120 KB |
Output is correct |
9 |
Correct |
10 ms |
5376 KB |
Output is correct |
10 |
Correct |
10 ms |
5376 KB |
Output is correct |
11 |
Correct |
10 ms |
5376 KB |
Output is correct |
12 |
Correct |
12 ms |
5376 KB |
Output is correct |
13 |
Correct |
10 ms |
5376 KB |
Output is correct |
14 |
Correct |
11 ms |
5376 KB |
Output is correct |
15 |
Correct |
10 ms |
5376 KB |
Output is correct |
16 |
Correct |
382 ms |
27816 KB |
Output is correct |
17 |
Correct |
800 ms |
49688 KB |
Output is correct |
18 |
Correct |
62 ms |
9904 KB |
Output is correct |
19 |
Correct |
364 ms |
33088 KB |
Output is correct |
20 |
Correct |
789 ms |
49816 KB |
Output is correct |
21 |
Correct |
511 ms |
37744 KB |
Output is correct |
22 |
Correct |
394 ms |
36504 KB |
Output is correct |
23 |
Correct |
816 ms |
49624 KB |
Output is correct |
24 |
Correct |
766 ms |
49688 KB |
Output is correct |
25 |
Correct |
763 ms |
49812 KB |
Output is correct |
26 |
Correct |
355 ms |
32912 KB |
Output is correct |
27 |
Correct |
365 ms |
33032 KB |
Output is correct |
28 |
Correct |
386 ms |
32780 KB |
Output is correct |
29 |
Correct |
359 ms |
33036 KB |
Output is correct |
30 |
Correct |
376 ms |
33168 KB |
Output is correct |
31 |
Correct |
8 ms |
5120 KB |
Output is correct |
32 |
Correct |
7 ms |
5120 KB |
Output is correct |
33 |
Correct |
8 ms |
5120 KB |
Output is correct |
34 |
Correct |
7 ms |
5120 KB |
Output is correct |
35 |
Correct |
8 ms |
5120 KB |
Output is correct |
36 |
Correct |
8 ms |
5120 KB |
Output is correct |
37 |
Correct |
7 ms |
5120 KB |
Output is correct |
38 |
Correct |
7 ms |
5120 KB |
Output is correct |
39 |
Correct |
9 ms |
5120 KB |
Output is correct |
40 |
Correct |
8 ms |
5120 KB |
Output is correct |
41 |
Correct |
284 ms |
35756 KB |
Output is correct |
42 |
Correct |
524 ms |
49360 KB |
Output is correct |
43 |
Correct |
494 ms |
49368 KB |
Output is correct |
44 |
Correct |
158 ms |
32680 KB |
Output is correct |
45 |
Correct |
517 ms |
49304 KB |
Output is correct |
46 |
Correct |
520 ms |
49432 KB |
Output is correct |
47 |
Correct |
514 ms |
49304 KB |
Output is correct |
48 |
Correct |
495 ms |
49276 KB |
Output is correct |
49 |
Correct |
496 ms |
49304 KB |
Output is correct |
50 |
Correct |
490 ms |
49348 KB |
Output is correct |
51 |
Correct |
495 ms |
49400 KB |
Output is correct |
52 |
Correct |
504 ms |
49292 KB |
Output is correct |
53 |
Correct |
503 ms |
49432 KB |
Output is correct |
54 |
Correct |
530 ms |
49584 KB |
Output is correct |
55 |
Correct |
517 ms |
50460 KB |
Output is correct |
56 |
Correct |
554 ms |
49512 KB |
Output is correct |
57 |
Correct |
518 ms |
49432 KB |
Output is correct |
58 |
Correct |
505 ms |
49432 KB |
Output is correct |
59 |
Correct |
140 ms |
34220 KB |
Output is correct |
60 |
Correct |
536 ms |
49436 KB |
Output is correct |
61 |
Correct |
470 ms |
49688 KB |
Output is correct |
62 |
Correct |
133 ms |
31368 KB |
Output is correct |
63 |
Correct |
149 ms |
31376 KB |
Output is correct |
64 |
Correct |
125 ms |
31376 KB |
Output is correct |
65 |
Correct |
130 ms |
31496 KB |
Output is correct |
66 |
Correct |
163 ms |
31532 KB |
Output is correct |
67 |
Correct |
169 ms |
34088 KB |
Output is correct |
68 |
Correct |
127 ms |
31380 KB |
Output is correct |
69 |
Correct |
155 ms |
33324 KB |
Output is correct |
70 |
Correct |
124 ms |
31372 KB |
Output is correct |
71 |
Correct |
152 ms |
33320 KB |
Output is correct |
72 |
Correct |
536 ms |
37664 KB |
Output is correct |
73 |
Correct |
771 ms |
50076 KB |
Output is correct |
74 |
Correct |
795 ms |
50256 KB |
Output is correct |
75 |
Correct |
815 ms |
50072 KB |
Output is correct |
76 |
Correct |
816 ms |
50072 KB |
Output is correct |
77 |
Correct |
812 ms |
50204 KB |
Output is correct |
78 |
Correct |
764 ms |
50072 KB |
Output is correct |
79 |
Correct |
809 ms |
50204 KB |
Output is correct |
80 |
Correct |
759 ms |
50072 KB |
Output is correct |
81 |
Correct |
795 ms |
50200 KB |
Output is correct |
82 |
Correct |
752 ms |
50328 KB |
Output is correct |
83 |
Correct |
797 ms |
50200 KB |
Output is correct |
84 |
Correct |
776 ms |
50340 KB |
Output is correct |
85 |
Correct |
814 ms |
51096 KB |
Output is correct |
86 |
Correct |
761 ms |
50328 KB |
Output is correct |
87 |
Correct |
782 ms |
50328 KB |
Output is correct |
88 |
Correct |
761 ms |
50588 KB |
Output is correct |
89 |
Correct |
502 ms |
35496 KB |
Output is correct |
90 |
Correct |
771 ms |
50328 KB |
Output is correct |
91 |
Correct |
739 ms |
50760 KB |
Output is correct |
92 |
Correct |
394 ms |
32900 KB |
Output is correct |
93 |
Correct |
450 ms |
33348 KB |
Output is correct |
94 |
Correct |
386 ms |
32908 KB |
Output is correct |
95 |
Correct |
368 ms |
32904 KB |
Output is correct |
96 |
Correct |
460 ms |
33196 KB |
Output is correct |
97 |
Correct |
532 ms |
34604 KB |
Output is correct |
98 |
Correct |
383 ms |
32936 KB |
Output is correct |
99 |
Correct |
535 ms |
35840 KB |
Output is correct |
100 |
Correct |
374 ms |
32908 KB |
Output is correct |