#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e15 + 7;
template<class T> inline void fix(T &x) {if(labs(x) >= mod) {x %= mod;} if(x < 0) {x += mod;}}
#define out(x) cout << __LINE__ << ": " << (#x) << " = " << (x) << endl
const ll MAX_N = 1e5 + 110, MAX_LOG = 20;
struct Lca {
vector<pair<int, ll> > g[MAX_N];
ll par[MAX_N][MAX_LOG], mx[MAX_N][MAX_LOG], d[MAX_N];
void add(int a, int b, ll c) {
g[a].push_back({b, c});
g[b].push_back({a, c});
}
void pre(int x, int p, ll w) {//Initialize lca with pre(root, 0, 0);
par[x][0] = p;
mx[x][0] = w;
d[x] = d[p] + 1;
for(int i = 1; i < MAX_LOG; i ++) {
par[x][i] = par[par[x][i - 1]][i - 1];
mx[x][i] = min(mx[par[x][i - 1]][i - 1], mx[x][i - 1]);
}
for(auto it : g[x]) {
if(it.first == p) {continue;}
pre(it.first, x, it.second);
}
}
ll ans(int a, int b) {
if(d[a] < d[b]) {swap(a, b);}
ll ret = mod;
for(int i = MAX_LOG - 1; i >= 0; i --) {
if(d[a] >= d[b] + (1 << i)) {
chkmin(ret, mx[a][i]);
a = par[a][i];
}
}
if(a == b) {return ret;}
for(int i = MAX_LOG - 1; i >= 0; i --) {
if(par[a][i] != par[b][i]) {
chkmin(ret, min(mx[a][i], mx[b][i]));
a = par[a][i];
b = par[b][i];
}
}
return min({ret, mx[a][0], mx[b][0]});
}
};
ll dist[MAX_N];
vector<pair<ll, pair<ll, ll> > > edges;
vector<pair<ll, ll> > g[MAX_N];
void dij(vector<ll> &st) {
fill_n(dist, MAX_N, mod);
priority_queue<pair<ll, ll> > pq;
for(auto it : st) {
dist[it] = 0;
pq.push({0, it});
}
while(!pq.empty()) {
auto curr = pq.top(); pq.pop();
if(-curr.first != dist[curr.second]) {continue;}
curr.first *= -1;
for(auto it : g[curr.second]) {
if(curr.first + it.second < dist[it.first]) {
dist[it.first] = curr.first + it.second;
pq.push({-curr.first + -it.second, it.first});
}
}
}
}
ll par[MAX_N], sz[MAX_N];
void init(ll n) {
for(ll i = 1; i <= n; i ++) {
par[i] = i;
sz[i] = 1;
}
}
ll find(ll x) {
if(x == par[x]) {
return x;
} else {
return par[x] = find(par[x]);
}
}
bool merge(ll x, ll y) {
x = find(x); y = find(y);
if(x == y) {return false;}
if(sz[x] < sz[y]) {swap(x, y);}
assert(sz[x] >= sz[y]);
par[y] = x;
sz[x] += sz[y];
return true;
}
ll ans[MAX_N];
Lca lca;
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
ll n, m;
cin >> n >> m;
for(ll i = 0; i < m; i ++) {
ll a, b, c;
cin >> a >> b >> c;
g[a].push_back({b, c});
g[b].push_back({a, c});
edges.push_back({-1, {a, b}});
}
ll k;
cin >> k;
vector<ll> st;
for(ll i = 0; i < k; i ++) {
ll a;
cin >> a;
st.push_back(a);
}
dij(st);
for(auto &it : edges) {
it.first = min(dist[it.second.first], dist[it.second.second]);
}
sort(edges.begin(), edges.end());
reverse(edges.begin(), edges.end());
init(n);
for(auto it : edges) {
if(merge(it.second.first, it.second.second)) {
lca.add(it.second.first, it.second.second, it.first);
}
}
lca.pre(1, 0, mod);
int q;
cin >> q;
for(int i = 0; i < q; i ++) {
int a, b;
cin >> a >> b;
cout << lca.ans(a, b) << endl;;
}
return 0;
}
/*
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 |
4 ms |
5888 KB |
Output is correct |
2 |
Correct |
5 ms |
6272 KB |
Output is correct |
3 |
Correct |
5 ms |
6272 KB |
Output is correct |
4 |
Correct |
4 ms |
5888 KB |
Output is correct |
5 |
Correct |
6 ms |
6272 KB |
Output is correct |
6 |
Correct |
5 ms |
6400 KB |
Output is correct |
7 |
Correct |
4 ms |
5888 KB |
Output is correct |
8 |
Correct |
4 ms |
5888 KB |
Output is correct |
9 |
Correct |
5 ms |
6272 KB |
Output is correct |
10 |
Correct |
5 ms |
6400 KB |
Output is correct |
11 |
Correct |
5 ms |
6272 KB |
Output is correct |
12 |
Correct |
6 ms |
6272 KB |
Output is correct |
13 |
Correct |
5 ms |
6272 KB |
Output is correct |
14 |
Correct |
6 ms |
6272 KB |
Output is correct |
15 |
Correct |
5 ms |
6272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5888 KB |
Output is correct |
2 |
Correct |
5 ms |
6272 KB |
Output is correct |
3 |
Correct |
5 ms |
6272 KB |
Output is correct |
4 |
Correct |
4 ms |
5888 KB |
Output is correct |
5 |
Correct |
6 ms |
6272 KB |
Output is correct |
6 |
Correct |
5 ms |
6400 KB |
Output is correct |
7 |
Correct |
4 ms |
5888 KB |
Output is correct |
8 |
Correct |
4 ms |
5888 KB |
Output is correct |
9 |
Correct |
5 ms |
6272 KB |
Output is correct |
10 |
Correct |
5 ms |
6400 KB |
Output is correct |
11 |
Correct |
5 ms |
6272 KB |
Output is correct |
12 |
Correct |
6 ms |
6272 KB |
Output is correct |
13 |
Correct |
5 ms |
6272 KB |
Output is correct |
14 |
Correct |
6 ms |
6272 KB |
Output is correct |
15 |
Correct |
5 ms |
6272 KB |
Output is correct |
16 |
Correct |
241 ms |
44836 KB |
Output is correct |
17 |
Correct |
693 ms |
90760 KB |
Output is correct |
18 |
Correct |
45 ms |
14380 KB |
Output is correct |
19 |
Correct |
176 ms |
54576 KB |
Output is correct |
20 |
Correct |
707 ms |
90888 KB |
Output is correct |
21 |
Correct |
421 ms |
64664 KB |
Output is correct |
22 |
Correct |
246 ms |
59684 KB |
Output is correct |
23 |
Correct |
702 ms |
90760 KB |
Output is correct |
24 |
Correct |
728 ms |
90760 KB |
Output is correct |
25 |
Correct |
698 ms |
90924 KB |
Output is correct |
26 |
Correct |
181 ms |
54344 KB |
Output is correct |
27 |
Correct |
184 ms |
54656 KB |
Output is correct |
28 |
Correct |
177 ms |
54336 KB |
Output is correct |
29 |
Correct |
178 ms |
54460 KB |
Output is correct |
30 |
Correct |
182 ms |
54584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5888 KB |
Output is correct |
2 |
Correct |
4 ms |
5888 KB |
Output is correct |
3 |
Correct |
4 ms |
5888 KB |
Output is correct |
4 |
Correct |
4 ms |
5888 KB |
Output is correct |
5 |
Correct |
4 ms |
5888 KB |
Output is correct |
6 |
Correct |
5 ms |
5888 KB |
Output is correct |
7 |
Correct |
4 ms |
5888 KB |
Output is correct |
8 |
Correct |
4 ms |
5888 KB |
Output is correct |
9 |
Correct |
5 ms |
5888 KB |
Output is correct |
10 |
Correct |
4 ms |
5888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
332 ms |
59032 KB |
Output is correct |
2 |
Correct |
621 ms |
89096 KB |
Output is correct |
3 |
Correct |
638 ms |
88968 KB |
Output is correct |
4 |
Correct |
185 ms |
55844 KB |
Output is correct |
5 |
Correct |
615 ms |
89064 KB |
Output is correct |
6 |
Correct |
634 ms |
89340 KB |
Output is correct |
7 |
Correct |
622 ms |
89128 KB |
Output is correct |
8 |
Correct |
610 ms |
89136 KB |
Output is correct |
9 |
Correct |
620 ms |
89096 KB |
Output is correct |
10 |
Correct |
623 ms |
89116 KB |
Output is correct |
11 |
Correct |
624 ms |
89100 KB |
Output is correct |
12 |
Correct |
643 ms |
89184 KB |
Output is correct |
13 |
Correct |
627 ms |
89100 KB |
Output is correct |
14 |
Correct |
619 ms |
89352 KB |
Output is correct |
15 |
Correct |
621 ms |
91480 KB |
Output is correct |
16 |
Correct |
616 ms |
89316 KB |
Output is correct |
17 |
Correct |
614 ms |
89008 KB |
Output is correct |
18 |
Correct |
605 ms |
89116 KB |
Output is correct |
19 |
Correct |
181 ms |
57376 KB |
Output is correct |
20 |
Correct |
615 ms |
89096 KB |
Output is correct |
21 |
Correct |
619 ms |
89480 KB |
Output is correct |
22 |
Correct |
135 ms |
52960 KB |
Output is correct |
23 |
Correct |
172 ms |
54180 KB |
Output is correct |
24 |
Correct |
133 ms |
52940 KB |
Output is correct |
25 |
Correct |
133 ms |
52916 KB |
Output is correct |
26 |
Correct |
195 ms |
54564 KB |
Output is correct |
27 |
Correct |
197 ms |
57120 KB |
Output is correct |
28 |
Correct |
130 ms |
52932 KB |
Output is correct |
29 |
Correct |
190 ms |
56508 KB |
Output is correct |
30 |
Correct |
134 ms |
52916 KB |
Output is correct |
31 |
Correct |
197 ms |
56484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5888 KB |
Output is correct |
2 |
Correct |
5 ms |
6272 KB |
Output is correct |
3 |
Correct |
5 ms |
6272 KB |
Output is correct |
4 |
Correct |
4 ms |
5888 KB |
Output is correct |
5 |
Correct |
6 ms |
6272 KB |
Output is correct |
6 |
Correct |
5 ms |
6400 KB |
Output is correct |
7 |
Correct |
4 ms |
5888 KB |
Output is correct |
8 |
Correct |
4 ms |
5888 KB |
Output is correct |
9 |
Correct |
5 ms |
6272 KB |
Output is correct |
10 |
Correct |
5 ms |
6400 KB |
Output is correct |
11 |
Correct |
5 ms |
6272 KB |
Output is correct |
12 |
Correct |
6 ms |
6272 KB |
Output is correct |
13 |
Correct |
5 ms |
6272 KB |
Output is correct |
14 |
Correct |
6 ms |
6272 KB |
Output is correct |
15 |
Correct |
5 ms |
6272 KB |
Output is correct |
16 |
Correct |
241 ms |
44836 KB |
Output is correct |
17 |
Correct |
693 ms |
90760 KB |
Output is correct |
18 |
Correct |
45 ms |
14380 KB |
Output is correct |
19 |
Correct |
176 ms |
54576 KB |
Output is correct |
20 |
Correct |
707 ms |
90888 KB |
Output is correct |
21 |
Correct |
421 ms |
64664 KB |
Output is correct |
22 |
Correct |
246 ms |
59684 KB |
Output is correct |
23 |
Correct |
702 ms |
90760 KB |
Output is correct |
24 |
Correct |
728 ms |
90760 KB |
Output is correct |
25 |
Correct |
698 ms |
90924 KB |
Output is correct |
26 |
Correct |
181 ms |
54344 KB |
Output is correct |
27 |
Correct |
184 ms |
54656 KB |
Output is correct |
28 |
Correct |
177 ms |
54336 KB |
Output is correct |
29 |
Correct |
178 ms |
54460 KB |
Output is correct |
30 |
Correct |
182 ms |
54584 KB |
Output is correct |
31 |
Correct |
4 ms |
5888 KB |
Output is correct |
32 |
Correct |
4 ms |
5888 KB |
Output is correct |
33 |
Correct |
4 ms |
5888 KB |
Output is correct |
34 |
Correct |
4 ms |
5888 KB |
Output is correct |
35 |
Correct |
4 ms |
5888 KB |
Output is correct |
36 |
Correct |
5 ms |
5888 KB |
Output is correct |
37 |
Correct |
4 ms |
5888 KB |
Output is correct |
38 |
Correct |
4 ms |
5888 KB |
Output is correct |
39 |
Correct |
5 ms |
5888 KB |
Output is correct |
40 |
Correct |
4 ms |
5888 KB |
Output is correct |
41 |
Correct |
332 ms |
59032 KB |
Output is correct |
42 |
Correct |
621 ms |
89096 KB |
Output is correct |
43 |
Correct |
638 ms |
88968 KB |
Output is correct |
44 |
Correct |
185 ms |
55844 KB |
Output is correct |
45 |
Correct |
615 ms |
89064 KB |
Output is correct |
46 |
Correct |
634 ms |
89340 KB |
Output is correct |
47 |
Correct |
622 ms |
89128 KB |
Output is correct |
48 |
Correct |
610 ms |
89136 KB |
Output is correct |
49 |
Correct |
620 ms |
89096 KB |
Output is correct |
50 |
Correct |
623 ms |
89116 KB |
Output is correct |
51 |
Correct |
624 ms |
89100 KB |
Output is correct |
52 |
Correct |
643 ms |
89184 KB |
Output is correct |
53 |
Correct |
627 ms |
89100 KB |
Output is correct |
54 |
Correct |
619 ms |
89352 KB |
Output is correct |
55 |
Correct |
621 ms |
91480 KB |
Output is correct |
56 |
Correct |
616 ms |
89316 KB |
Output is correct |
57 |
Correct |
614 ms |
89008 KB |
Output is correct |
58 |
Correct |
605 ms |
89116 KB |
Output is correct |
59 |
Correct |
181 ms |
57376 KB |
Output is correct |
60 |
Correct |
615 ms |
89096 KB |
Output is correct |
61 |
Correct |
619 ms |
89480 KB |
Output is correct |
62 |
Correct |
135 ms |
52960 KB |
Output is correct |
63 |
Correct |
172 ms |
54180 KB |
Output is correct |
64 |
Correct |
133 ms |
52940 KB |
Output is correct |
65 |
Correct |
133 ms |
52916 KB |
Output is correct |
66 |
Correct |
195 ms |
54564 KB |
Output is correct |
67 |
Correct |
197 ms |
57120 KB |
Output is correct |
68 |
Correct |
130 ms |
52932 KB |
Output is correct |
69 |
Correct |
190 ms |
56508 KB |
Output is correct |
70 |
Correct |
134 ms |
52916 KB |
Output is correct |
71 |
Correct |
197 ms |
56484 KB |
Output is correct |
72 |
Correct |
423 ms |
64028 KB |
Output is correct |
73 |
Correct |
688 ms |
90760 KB |
Output is correct |
74 |
Correct |
703 ms |
90764 KB |
Output is correct |
75 |
Correct |
705 ms |
90788 KB |
Output is correct |
76 |
Correct |
696 ms |
90908 KB |
Output is correct |
77 |
Correct |
695 ms |
90756 KB |
Output is correct |
78 |
Correct |
712 ms |
90668 KB |
Output is correct |
79 |
Correct |
704 ms |
90760 KB |
Output is correct |
80 |
Correct |
710 ms |
90636 KB |
Output is correct |
81 |
Correct |
724 ms |
90828 KB |
Output is correct |
82 |
Correct |
701 ms |
90764 KB |
Output is correct |
83 |
Correct |
707 ms |
91016 KB |
Output is correct |
84 |
Correct |
701 ms |
91016 KB |
Output is correct |
85 |
Correct |
723 ms |
92828 KB |
Output is correct |
86 |
Correct |
699 ms |
90804 KB |
Output is correct |
87 |
Correct |
703 ms |
90900 KB |
Output is correct |
88 |
Correct |
709 ms |
90776 KB |
Output is correct |
89 |
Correct |
322 ms |
58788 KB |
Output is correct |
90 |
Correct |
735 ms |
90760 KB |
Output is correct |
91 |
Correct |
717 ms |
90888 KB |
Output is correct |
92 |
Correct |
213 ms |
54460 KB |
Output is correct |
93 |
Correct |
310 ms |
56224 KB |
Output is correct |
94 |
Correct |
200 ms |
54348 KB |
Output is correct |
95 |
Correct |
205 ms |
54460 KB |
Output is correct |
96 |
Correct |
314 ms |
55716 KB |
Output is correct |
97 |
Correct |
339 ms |
57636 KB |
Output is correct |
98 |
Correct |
201 ms |
54348 KB |
Output is correct |
99 |
Correct |
335 ms |
58916 KB |
Output is correct |
100 |
Correct |
205 ms |
54588 KB |
Output is correct |