#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;
class UnionFind{
public:
vi p,r;
UnionFind(ll n){
p.resize(n);
rep(i,0,n) p[i] = i;
r.resize(n,1);
}
ll find(ll a){
return p[a]==a?a:p[a]=find(p[a]);
}
void join(ll a,ll b){
a = find(a);
b = find(b);
if(r[a]>r[b]){
p[b] = a;
} else if(r[b]>r[a]){
p[a] = b;
} else {
p[a] = b;
r[b]++;
}
}
};
ll n,k;
vector<vector<pii>> ge;
vi g;
vi dist;
void getDists(){
dist.resize(n,-1);
set<pii> q;
rep(i,0,k) q.emplace(0,g[i]);
while(q.size()){
ll v = q.begin()->second;
ll d = q.begin()->first;
q.erase(q.begin());
if(dist[v]!=-1) continue;
dist[v] = d;
rep(i,0,ge[v].size()){
q.emplace(d+ge[v][i].second,ge[v][i].first);
}
}
}
vector<vector<pii>> e;
void makeTree(){
vector<tuple<ll,ll,ll> > edges;
rep(i,0,n){
rep(j,0,ge[i].size()){
edges.emplace_back(min(dist[ge[i][j].first],dist[i]),i,ge[i][j].first);
}
}
sort(all(edges));
reverse(all(edges));
UnionFind uf(n);
e.resize(n);
rep(i,0,edges.size()){
ll a,b,w;
tie(w,a,b) = edges[i];
if(uf.find(a)!=uf.find(b)){
uf.join(a,b);
e[a].emplace_back(b,w);
e[b].emplace_back(a,w);
}
}
}
class LCA {
public:
vi levels;
vector<vector<pii> > jump;
LCA(){
jump.resize(30,vector<pii>(n));
levels.resize(n);
dfs(0,0,0,1e18);
rep(i,1,30){
rep(j,0,n){
jump[i][j].first = jump[i-1][jump[i-1][j].first].first;
jump[i][j].second = min(jump[i-1][j].second,jump[i-1][jump[i-1][j].first].second);
}
}
}
void dfs(ll v,ll last,ll level,ll w){
jump[0][v] = {last,w};
levels[v] = level;
rep(i,0,e[v].size()){
if(e[v][i].first==last) continue;
dfs(e[v][i].first,v,level+1,e[v][i].second);
}
}
ll getMin(ll a,ll b){
ll mn = 1e18;
if(levels[a]<levels[b]) swap(a,b);
for(int i = 29; i>=0;--i){
if(levels[jump[i][a].first]>=levels[b]){
mn = min(mn,jump[i][a].second);
a = jump[i][a].first;
}
}
assert(levels[a]==levels[b]);
if(a==b) return mn;
for(int i = 29; i>=0;--i){
if(jump[i][a].first!=jump[i][b].first){
mn = min(mn,jump[i][a].second);
a = jump[i][a].first;
mn = min(mn,jump[i][b].second);
b = jump[i][b].first;
}
}
assert(a!=b);
mn = min(mn,jump[0][a].second);
a = jump[0][a].first;
mn = min(mn,jump[0][b].second);
b = jump[0][b].first;
assert(a==b);
return mn;
}
};
int main(){
cin.sync_with_stdio(false);
ll m;
cin>>n>>m;
ge.resize(n);
rep(i,0,m){
ll a,b,w;
cin>>a>>b>>w;
--a;--b;
ge[a].emplace_back(b,w);
ge[b].emplace_back(a,w);
}
cin>>k;
g.resize(k);
rep(i,0,k) {
cin>>g[i];
--g[i];
}
getDists();
//rep(i,0,n) cout<<i+1<<": "<<dist[i]<<endl;
makeTree();
/*cout<<"tree"<<endl;
rep(i,0,n){
cout<<i+1<<": ";
rep(j,0,e[i].size()){
cout<<e[i][j].first+1<<" ";
}
cout<<endl;
}*/
LCA* lca = new LCA();
ll q;
cin>>q;
rep(i,0,q){
ll a,b;
cin>>a>>b;
--a; --b;
cout<<lca->getMin(a,b)<<endl;
}
_Exit(0);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
6 ms |
1016 KB |
Output is correct |
3 |
Correct |
6 ms |
1016 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
7 ms |
1020 KB |
Output is correct |
6 |
Correct |
7 ms |
1016 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
7 ms |
1016 KB |
Output is correct |
10 |
Correct |
7 ms |
1016 KB |
Output is correct |
11 |
Correct |
7 ms |
988 KB |
Output is correct |
12 |
Correct |
6 ms |
1016 KB |
Output is correct |
13 |
Correct |
7 ms |
1016 KB |
Output is correct |
14 |
Correct |
7 ms |
1020 KB |
Output is correct |
15 |
Correct |
7 ms |
1020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
6 ms |
1016 KB |
Output is correct |
3 |
Correct |
6 ms |
1016 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
7 ms |
1020 KB |
Output is correct |
6 |
Correct |
7 ms |
1016 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
7 ms |
1016 KB |
Output is correct |
10 |
Correct |
7 ms |
1016 KB |
Output is correct |
11 |
Correct |
7 ms |
988 KB |
Output is correct |
12 |
Correct |
6 ms |
1016 KB |
Output is correct |
13 |
Correct |
7 ms |
1016 KB |
Output is correct |
14 |
Correct |
7 ms |
1020 KB |
Output is correct |
15 |
Correct |
7 ms |
1020 KB |
Output is correct |
16 |
Correct |
699 ms |
53164 KB |
Output is correct |
17 |
Correct |
2579 ms |
83148 KB |
Output is correct |
18 |
Correct |
125 ms |
9656 KB |
Output is correct |
19 |
Correct |
594 ms |
65800 KB |
Output is correct |
20 |
Correct |
2502 ms |
83212 KB |
Output is correct |
21 |
Correct |
1102 ms |
69656 KB |
Output is correct |
22 |
Correct |
563 ms |
69288 KB |
Output is correct |
23 |
Correct |
2496 ms |
83120 KB |
Output is correct |
24 |
Correct |
2547 ms |
83204 KB |
Output is correct |
25 |
Correct |
2646 ms |
83204 KB |
Output is correct |
26 |
Correct |
601 ms |
65672 KB |
Output is correct |
27 |
Correct |
593 ms |
65668 KB |
Output is correct |
28 |
Correct |
585 ms |
65532 KB |
Output is correct |
29 |
Correct |
588 ms |
65664 KB |
Output is correct |
30 |
Correct |
591 ms |
65840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
416 KB |
Output is correct |
9 |
Correct |
2 ms |
420 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
646 ms |
69132 KB |
Output is correct |
2 |
Correct |
1991 ms |
82660 KB |
Output is correct |
3 |
Correct |
1990 ms |
82724 KB |
Output is correct |
4 |
Correct |
202 ms |
65716 KB |
Output is correct |
5 |
Correct |
2131 ms |
82724 KB |
Output is correct |
6 |
Correct |
2163 ms |
82744 KB |
Output is correct |
7 |
Correct |
1970 ms |
82732 KB |
Output is correct |
8 |
Correct |
2131 ms |
83492 KB |
Output is correct |
9 |
Correct |
2029 ms |
83680 KB |
Output is correct |
10 |
Correct |
1944 ms |
83580 KB |
Output is correct |
11 |
Correct |
2096 ms |
83524 KB |
Output is correct |
12 |
Correct |
2052 ms |
83460 KB |
Output is correct |
13 |
Correct |
2077 ms |
83412 KB |
Output is correct |
14 |
Correct |
1978 ms |
83500 KB |
Output is correct |
15 |
Correct |
2075 ms |
83576 KB |
Output is correct |
16 |
Correct |
2262 ms |
82680 KB |
Output is correct |
17 |
Correct |
2171 ms |
82688 KB |
Output is correct |
18 |
Correct |
2001 ms |
82828 KB |
Output is correct |
19 |
Correct |
187 ms |
68352 KB |
Output is correct |
20 |
Correct |
2027 ms |
82740 KB |
Output is correct |
21 |
Correct |
1924 ms |
83372 KB |
Output is correct |
22 |
Correct |
218 ms |
65388 KB |
Output is correct |
23 |
Correct |
232 ms |
64908 KB |
Output is correct |
24 |
Correct |
227 ms |
65380 KB |
Output is correct |
25 |
Correct |
209 ms |
65340 KB |
Output is correct |
26 |
Correct |
255 ms |
65036 KB |
Output is correct |
27 |
Correct |
199 ms |
68308 KB |
Output is correct |
28 |
Correct |
215 ms |
65320 KB |
Output is correct |
29 |
Correct |
191 ms |
66088 KB |
Output is correct |
30 |
Correct |
218 ms |
65272 KB |
Output is correct |
31 |
Correct |
193 ms |
66088 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
6 ms |
1016 KB |
Output is correct |
3 |
Correct |
6 ms |
1016 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
7 ms |
1020 KB |
Output is correct |
6 |
Correct |
7 ms |
1016 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
7 ms |
1016 KB |
Output is correct |
10 |
Correct |
7 ms |
1016 KB |
Output is correct |
11 |
Correct |
7 ms |
988 KB |
Output is correct |
12 |
Correct |
6 ms |
1016 KB |
Output is correct |
13 |
Correct |
7 ms |
1016 KB |
Output is correct |
14 |
Correct |
7 ms |
1020 KB |
Output is correct |
15 |
Correct |
7 ms |
1020 KB |
Output is correct |
16 |
Correct |
699 ms |
53164 KB |
Output is correct |
17 |
Correct |
2579 ms |
83148 KB |
Output is correct |
18 |
Correct |
125 ms |
9656 KB |
Output is correct |
19 |
Correct |
594 ms |
65800 KB |
Output is correct |
20 |
Correct |
2502 ms |
83212 KB |
Output is correct |
21 |
Correct |
1102 ms |
69656 KB |
Output is correct |
22 |
Correct |
563 ms |
69288 KB |
Output is correct |
23 |
Correct |
2496 ms |
83120 KB |
Output is correct |
24 |
Correct |
2547 ms |
83204 KB |
Output is correct |
25 |
Correct |
2646 ms |
83204 KB |
Output is correct |
26 |
Correct |
601 ms |
65672 KB |
Output is correct |
27 |
Correct |
593 ms |
65668 KB |
Output is correct |
28 |
Correct |
585 ms |
65532 KB |
Output is correct |
29 |
Correct |
588 ms |
65664 KB |
Output is correct |
30 |
Correct |
591 ms |
65840 KB |
Output is correct |
31 |
Correct |
3 ms |
376 KB |
Output is correct |
32 |
Correct |
2 ms |
376 KB |
Output is correct |
33 |
Correct |
2 ms |
376 KB |
Output is correct |
34 |
Correct |
2 ms |
376 KB |
Output is correct |
35 |
Correct |
2 ms |
376 KB |
Output is correct |
36 |
Correct |
2 ms |
376 KB |
Output is correct |
37 |
Correct |
2 ms |
376 KB |
Output is correct |
38 |
Correct |
2 ms |
416 KB |
Output is correct |
39 |
Correct |
2 ms |
420 KB |
Output is correct |
40 |
Correct |
2 ms |
376 KB |
Output is correct |
41 |
Correct |
646 ms |
69132 KB |
Output is correct |
42 |
Correct |
1991 ms |
82660 KB |
Output is correct |
43 |
Correct |
1990 ms |
82724 KB |
Output is correct |
44 |
Correct |
202 ms |
65716 KB |
Output is correct |
45 |
Correct |
2131 ms |
82724 KB |
Output is correct |
46 |
Correct |
2163 ms |
82744 KB |
Output is correct |
47 |
Correct |
1970 ms |
82732 KB |
Output is correct |
48 |
Correct |
2131 ms |
83492 KB |
Output is correct |
49 |
Correct |
2029 ms |
83680 KB |
Output is correct |
50 |
Correct |
1944 ms |
83580 KB |
Output is correct |
51 |
Correct |
2096 ms |
83524 KB |
Output is correct |
52 |
Correct |
2052 ms |
83460 KB |
Output is correct |
53 |
Correct |
2077 ms |
83412 KB |
Output is correct |
54 |
Correct |
1978 ms |
83500 KB |
Output is correct |
55 |
Correct |
2075 ms |
83576 KB |
Output is correct |
56 |
Correct |
2262 ms |
82680 KB |
Output is correct |
57 |
Correct |
2171 ms |
82688 KB |
Output is correct |
58 |
Correct |
2001 ms |
82828 KB |
Output is correct |
59 |
Correct |
187 ms |
68352 KB |
Output is correct |
60 |
Correct |
2027 ms |
82740 KB |
Output is correct |
61 |
Correct |
1924 ms |
83372 KB |
Output is correct |
62 |
Correct |
218 ms |
65388 KB |
Output is correct |
63 |
Correct |
232 ms |
64908 KB |
Output is correct |
64 |
Correct |
227 ms |
65380 KB |
Output is correct |
65 |
Correct |
209 ms |
65340 KB |
Output is correct |
66 |
Correct |
255 ms |
65036 KB |
Output is correct |
67 |
Correct |
199 ms |
68308 KB |
Output is correct |
68 |
Correct |
215 ms |
65320 KB |
Output is correct |
69 |
Correct |
191 ms |
66088 KB |
Output is correct |
70 |
Correct |
218 ms |
65272 KB |
Output is correct |
71 |
Correct |
193 ms |
66088 KB |
Output is correct |
72 |
Correct |
1167 ms |
70304 KB |
Output is correct |
73 |
Correct |
2485 ms |
83868 KB |
Output is correct |
74 |
Correct |
2607 ms |
86468 KB |
Output is correct |
75 |
Correct |
2435 ms |
86872 KB |
Output is correct |
76 |
Correct |
2607 ms |
86916 KB |
Output is correct |
77 |
Correct |
2693 ms |
86648 KB |
Output is correct |
78 |
Correct |
2509 ms |
86520 KB |
Output is correct |
79 |
Correct |
2568 ms |
87104 KB |
Output is correct |
80 |
Correct |
2668 ms |
86604 KB |
Output is correct |
81 |
Correct |
2567 ms |
86940 KB |
Output is correct |
82 |
Correct |
2593 ms |
86144 KB |
Output is correct |
83 |
Correct |
2591 ms |
86480 KB |
Output is correct |
84 |
Correct |
2692 ms |
86824 KB |
Output is correct |
85 |
Correct |
2541 ms |
86652 KB |
Output is correct |
86 |
Correct |
2855 ms |
86844 KB |
Output is correct |
87 |
Correct |
2540 ms |
86368 KB |
Output is correct |
88 |
Correct |
2468 ms |
87388 KB |
Output is correct |
89 |
Correct |
874 ms |
70520 KB |
Output is correct |
90 |
Correct |
2618 ms |
87024 KB |
Output is correct |
91 |
Correct |
2486 ms |
87264 KB |
Output is correct |
92 |
Correct |
636 ms |
67896 KB |
Output is correct |
93 |
Correct |
774 ms |
69856 KB |
Output is correct |
94 |
Correct |
647 ms |
67596 KB |
Output is correct |
95 |
Correct |
626 ms |
67616 KB |
Output is correct |
96 |
Correct |
780 ms |
67528 KB |
Output is correct |
97 |
Correct |
767 ms |
69840 KB |
Output is correct |
98 |
Correct |
631 ms |
66948 KB |
Output is correct |
99 |
Correct |
733 ms |
68972 KB |
Output is correct |
100 |
Correct |
633 ms |
67284 KB |
Output is correct |