#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
const int lg = 25;
int dist[maxn], rt[maxn];
vector<pair<int, int>> graf[maxn];
int root(int u) {
return rt[u] == u ? u : rt[u] = root(rt[u]);
}
int par[maxn][lg], dep[maxn];
int st[maxn][lg];
vector<pair<int, int>> tree[maxn];
void Dfs(int u, int p) {
par[u][0] = p;
for (int i = 1; i < lg; ++i) {
if (par[u][i - 1] != -1) {
par[u][i] = par[par[u][i - 1]][i - 1];
}
}
for (int i = 1; i < lg; ++i) {
if (par[u][i - 1] != -1) {
st[u][i] = min(st[u][i - 1], st[par[u][i - 1]][i - 1]);
}
}
for (auto c : tree[u]) {
int v = c.first;
int w = c.second;
if (v == p) continue;
st[v][0] = w;
dep[v] = dep[u] + 1;
Dfs(v, u);
}
}
int Lca(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
for (int i = lg - 1; ~i; --i) {
if (par[u][i] != -1 && dep[par[u][i]] >= dep[v]) {
u = par[u][i];
}
}
if (u == v) return u;
for (int i = lg - 1; ~i; --i) {
if (par[u][i] != par[v][i]) {
u = par[u][i];
v = par[v][i];
}
}
return (u == v ? u : par[u][0]);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(11);
cerr << fixed << setprecision(6);
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i)
rt[i] = i;
vector<int> a(m), b(m), w(m);
for (int i = 0; i < m; ++i) {
cin >> a[i] >> b[i] >> w[i];
--a[i]; --b[i];
graf[a[i]].push_back({b[i], w[i]});
graf[b[i]].push_back({a[i], w[i]});
}
int k;
cin >> k;
for (int i = 0; i < n; ++i)
dist[i] = 1e9;
set<pair<int, int>> que;
for (int i = 0; i < k; ++i) {
int g;
cin >> g;
--g;
dist[g] = 0;
que.insert({0, g});
}
while (que.size()) {
auto it = que.begin();
int d = it -> first;
int u = it -> second;
que.erase(it);
if (d > dist[u]) continue;
for (auto c : graf[u]) {
int v = c.first;
int w = c.second;
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
que.insert({dist[v], v});
}
}
}
vector<tuple<int, int, int>> edges;
for (int i = 0; i < m; ++i) {
edges.push_back({min(dist[a[i]], dist[b[i]]), a[i], b[i]});
}
sort(edges.rbegin(), edges.rend());
for (int i = 0; i < m; ++i) {
int t = get<0>(edges[i]);
int u = get<1>(edges[i]);
int v = get<2>(edges[i]);
int par_u = root(u);
int par_v = root(v);
if (par_u == par_v) continue;
rt[par_v] = par_u;
tree[u].push_back({v, t});
tree[v].push_back({u, t});
}
Dfs(0, -1);
int q;
cin >> q;
while (q--) {
int s, t;
cin >> s >> t;
--s; --t;
int l = Lca(s, t), ans = dist[l];
for (int i = lg - 1; ~i; --i) {
if (par[s][i] != -1 && dep[par[s][i]] > dep[l]) {
ans = min(ans, st[s][i]);
s = par[s][i];
}
}
if (s != l)
ans = min(ans, st[s][0]);
for (int i = lg - 1; ~i; --i) {
if (par[t][i] != -1 && dep[par[t][i]] > dep[l]) {
ans = min(ans, st[t][i]);
t = par[t][i];
}
}
if (t != l)
ans = min(ans, st[t][0]);
cout << ans << "\n";
}
}
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
4 ms |
5336 KB |
Output is correct |
3 |
Correct |
4 ms |
5324 KB |
Output is correct |
4 |
Correct |
4 ms |
4940 KB |
Output is correct |
5 |
Correct |
4 ms |
5296 KB |
Output is correct |
6 |
Correct |
7 ms |
5300 KB |
Output is correct |
7 |
Correct |
4 ms |
5032 KB |
Output is correct |
8 |
Correct |
3 ms |
5068 KB |
Output is correct |
9 |
Correct |
5 ms |
5324 KB |
Output is correct |
10 |
Correct |
4 ms |
5324 KB |
Output is correct |
11 |
Correct |
5 ms |
5324 KB |
Output is correct |
12 |
Correct |
5 ms |
5292 KB |
Output is correct |
13 |
Correct |
5 ms |
5300 KB |
Output is correct |
14 |
Correct |
4 ms |
5340 KB |
Output is correct |
15 |
Correct |
5 ms |
5324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
4 ms |
5336 KB |
Output is correct |
3 |
Correct |
4 ms |
5324 KB |
Output is correct |
4 |
Correct |
4 ms |
4940 KB |
Output is correct |
5 |
Correct |
4 ms |
5296 KB |
Output is correct |
6 |
Correct |
7 ms |
5300 KB |
Output is correct |
7 |
Correct |
4 ms |
5032 KB |
Output is correct |
8 |
Correct |
3 ms |
5068 KB |
Output is correct |
9 |
Correct |
5 ms |
5324 KB |
Output is correct |
10 |
Correct |
4 ms |
5324 KB |
Output is correct |
11 |
Correct |
5 ms |
5324 KB |
Output is correct |
12 |
Correct |
5 ms |
5292 KB |
Output is correct |
13 |
Correct |
5 ms |
5300 KB |
Output is correct |
14 |
Correct |
4 ms |
5340 KB |
Output is correct |
15 |
Correct |
5 ms |
5324 KB |
Output is correct |
16 |
Correct |
234 ms |
32932 KB |
Output is correct |
17 |
Correct |
790 ms |
65972 KB |
Output is correct |
18 |
Correct |
42 ms |
10888 KB |
Output is correct |
19 |
Correct |
183 ms |
39516 KB |
Output is correct |
20 |
Correct |
759 ms |
65572 KB |
Output is correct |
21 |
Correct |
373 ms |
45028 KB |
Output is correct |
22 |
Correct |
254 ms |
45832 KB |
Output is correct |
23 |
Correct |
666 ms |
65968 KB |
Output is correct |
24 |
Correct |
689 ms |
66044 KB |
Output is correct |
25 |
Correct |
715 ms |
66296 KB |
Output is correct |
26 |
Correct |
209 ms |
39736 KB |
Output is correct |
27 |
Correct |
194 ms |
39992 KB |
Output is correct |
28 |
Correct |
246 ms |
39776 KB |
Output is correct |
29 |
Correct |
202 ms |
39540 KB |
Output is correct |
30 |
Correct |
223 ms |
40012 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
5028 KB |
Output is correct |
3 |
Correct |
4 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
4940 KB |
Output is correct |
5 |
Correct |
4 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
5028 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
3 ms |
4940 KB |
Output is correct |
10 |
Correct |
4 ms |
5024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
281 ms |
39868 KB |
Output is correct |
2 |
Correct |
717 ms |
64368 KB |
Output is correct |
3 |
Correct |
638 ms |
63252 KB |
Output is correct |
4 |
Correct |
175 ms |
40760 KB |
Output is correct |
5 |
Correct |
559 ms |
64400 KB |
Output is correct |
6 |
Correct |
538 ms |
64300 KB |
Output is correct |
7 |
Correct |
547 ms |
64396 KB |
Output is correct |
8 |
Correct |
564 ms |
64320 KB |
Output is correct |
9 |
Correct |
559 ms |
64444 KB |
Output is correct |
10 |
Correct |
637 ms |
63992 KB |
Output is correct |
11 |
Correct |
603 ms |
63804 KB |
Output is correct |
12 |
Correct |
549 ms |
64380 KB |
Output is correct |
13 |
Correct |
551 ms |
64284 KB |
Output is correct |
14 |
Correct |
563 ms |
64480 KB |
Output is correct |
15 |
Correct |
584 ms |
64584 KB |
Output is correct |
16 |
Correct |
604 ms |
64532 KB |
Output is correct |
17 |
Correct |
602 ms |
64416 KB |
Output is correct |
18 |
Correct |
582 ms |
64272 KB |
Output is correct |
19 |
Correct |
162 ms |
43324 KB |
Output is correct |
20 |
Correct |
556 ms |
62008 KB |
Output is correct |
21 |
Correct |
472 ms |
63080 KB |
Output is correct |
22 |
Correct |
120 ms |
38300 KB |
Output is correct |
23 |
Correct |
138 ms |
37868 KB |
Output is correct |
24 |
Correct |
115 ms |
38324 KB |
Output is correct |
25 |
Correct |
151 ms |
37956 KB |
Output is correct |
26 |
Correct |
165 ms |
38384 KB |
Output is correct |
27 |
Correct |
155 ms |
43068 KB |
Output is correct |
28 |
Correct |
148 ms |
38328 KB |
Output is correct |
29 |
Correct |
154 ms |
41916 KB |
Output is correct |
30 |
Correct |
128 ms |
38324 KB |
Output is correct |
31 |
Correct |
163 ms |
42012 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
4 ms |
5336 KB |
Output is correct |
3 |
Correct |
4 ms |
5324 KB |
Output is correct |
4 |
Correct |
4 ms |
4940 KB |
Output is correct |
5 |
Correct |
4 ms |
5296 KB |
Output is correct |
6 |
Correct |
7 ms |
5300 KB |
Output is correct |
7 |
Correct |
4 ms |
5032 KB |
Output is correct |
8 |
Correct |
3 ms |
5068 KB |
Output is correct |
9 |
Correct |
5 ms |
5324 KB |
Output is correct |
10 |
Correct |
4 ms |
5324 KB |
Output is correct |
11 |
Correct |
5 ms |
5324 KB |
Output is correct |
12 |
Correct |
5 ms |
5292 KB |
Output is correct |
13 |
Correct |
5 ms |
5300 KB |
Output is correct |
14 |
Correct |
4 ms |
5340 KB |
Output is correct |
15 |
Correct |
5 ms |
5324 KB |
Output is correct |
16 |
Correct |
234 ms |
32932 KB |
Output is correct |
17 |
Correct |
790 ms |
65972 KB |
Output is correct |
18 |
Correct |
42 ms |
10888 KB |
Output is correct |
19 |
Correct |
183 ms |
39516 KB |
Output is correct |
20 |
Correct |
759 ms |
65572 KB |
Output is correct |
21 |
Correct |
373 ms |
45028 KB |
Output is correct |
22 |
Correct |
254 ms |
45832 KB |
Output is correct |
23 |
Correct |
666 ms |
65968 KB |
Output is correct |
24 |
Correct |
689 ms |
66044 KB |
Output is correct |
25 |
Correct |
715 ms |
66296 KB |
Output is correct |
26 |
Correct |
209 ms |
39736 KB |
Output is correct |
27 |
Correct |
194 ms |
39992 KB |
Output is correct |
28 |
Correct |
246 ms |
39776 KB |
Output is correct |
29 |
Correct |
202 ms |
39540 KB |
Output is correct |
30 |
Correct |
223 ms |
40012 KB |
Output is correct |
31 |
Correct |
3 ms |
4940 KB |
Output is correct |
32 |
Correct |
3 ms |
5028 KB |
Output is correct |
33 |
Correct |
4 ms |
4940 KB |
Output is correct |
34 |
Correct |
3 ms |
4940 KB |
Output is correct |
35 |
Correct |
4 ms |
4940 KB |
Output is correct |
36 |
Correct |
3 ms |
5028 KB |
Output is correct |
37 |
Correct |
3 ms |
4940 KB |
Output is correct |
38 |
Correct |
3 ms |
4940 KB |
Output is correct |
39 |
Correct |
3 ms |
4940 KB |
Output is correct |
40 |
Correct |
4 ms |
5024 KB |
Output is correct |
41 |
Correct |
281 ms |
39868 KB |
Output is correct |
42 |
Correct |
717 ms |
64368 KB |
Output is correct |
43 |
Correct |
638 ms |
63252 KB |
Output is correct |
44 |
Correct |
175 ms |
40760 KB |
Output is correct |
45 |
Correct |
559 ms |
64400 KB |
Output is correct |
46 |
Correct |
538 ms |
64300 KB |
Output is correct |
47 |
Correct |
547 ms |
64396 KB |
Output is correct |
48 |
Correct |
564 ms |
64320 KB |
Output is correct |
49 |
Correct |
559 ms |
64444 KB |
Output is correct |
50 |
Correct |
637 ms |
63992 KB |
Output is correct |
51 |
Correct |
603 ms |
63804 KB |
Output is correct |
52 |
Correct |
549 ms |
64380 KB |
Output is correct |
53 |
Correct |
551 ms |
64284 KB |
Output is correct |
54 |
Correct |
563 ms |
64480 KB |
Output is correct |
55 |
Correct |
584 ms |
64584 KB |
Output is correct |
56 |
Correct |
604 ms |
64532 KB |
Output is correct |
57 |
Correct |
602 ms |
64416 KB |
Output is correct |
58 |
Correct |
582 ms |
64272 KB |
Output is correct |
59 |
Correct |
162 ms |
43324 KB |
Output is correct |
60 |
Correct |
556 ms |
62008 KB |
Output is correct |
61 |
Correct |
472 ms |
63080 KB |
Output is correct |
62 |
Correct |
120 ms |
38300 KB |
Output is correct |
63 |
Correct |
138 ms |
37868 KB |
Output is correct |
64 |
Correct |
115 ms |
38324 KB |
Output is correct |
65 |
Correct |
151 ms |
37956 KB |
Output is correct |
66 |
Correct |
165 ms |
38384 KB |
Output is correct |
67 |
Correct |
155 ms |
43068 KB |
Output is correct |
68 |
Correct |
148 ms |
38328 KB |
Output is correct |
69 |
Correct |
154 ms |
41916 KB |
Output is correct |
70 |
Correct |
128 ms |
38324 KB |
Output is correct |
71 |
Correct |
163 ms |
42012 KB |
Output is correct |
72 |
Correct |
391 ms |
44888 KB |
Output is correct |
73 |
Correct |
668 ms |
66228 KB |
Output is correct |
74 |
Correct |
709 ms |
66228 KB |
Output is correct |
75 |
Correct |
640 ms |
66104 KB |
Output is correct |
76 |
Correct |
676 ms |
65996 KB |
Output is correct |
77 |
Correct |
697 ms |
65992 KB |
Output is correct |
78 |
Correct |
708 ms |
65660 KB |
Output is correct |
79 |
Correct |
699 ms |
65940 KB |
Output is correct |
80 |
Correct |
690 ms |
64828 KB |
Output is correct |
81 |
Correct |
689 ms |
65952 KB |
Output is correct |
82 |
Correct |
661 ms |
65260 KB |
Output is correct |
83 |
Correct |
688 ms |
65996 KB |
Output is correct |
84 |
Correct |
711 ms |
66272 KB |
Output is correct |
85 |
Correct |
717 ms |
66228 KB |
Output is correct |
86 |
Correct |
761 ms |
66004 KB |
Output is correct |
87 |
Correct |
760 ms |
66036 KB |
Output is correct |
88 |
Correct |
724 ms |
66060 KB |
Output is correct |
89 |
Correct |
357 ms |
44164 KB |
Output is correct |
90 |
Correct |
747 ms |
64712 KB |
Output is correct |
91 |
Correct |
611 ms |
64508 KB |
Output is correct |
92 |
Correct |
257 ms |
39480 KB |
Output is correct |
93 |
Correct |
302 ms |
40092 KB |
Output is correct |
94 |
Correct |
203 ms |
39736 KB |
Output is correct |
95 |
Correct |
225 ms |
39548 KB |
Output is correct |
96 |
Correct |
286 ms |
39304 KB |
Output is correct |
97 |
Correct |
361 ms |
42912 KB |
Output is correct |
98 |
Correct |
205 ms |
39324 KB |
Output is correct |
99 |
Correct |
352 ms |
44812 KB |
Output is correct |
100 |
Correct |
202 ms |
39476 KB |
Output is correct |