#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+7;
vector<int> g[N],cost[N];
int di[N];
bool used[N];
int par[N];
int fpar(int v){
return v==par[v] ?v:par[v]=fpar(par[v]);
}
int up[N][25],val[N][25];
int tin[N],tout[N],ti=0;
void dfs(int v,int p){
tin[v]=++ti;
up[v][0]=p;
val[v][0]=min(di[v],di[p]);
for(int i=1;i<=20;++i){up[v][i]=up[up[v][i-1]][i-1];val[v][i]=min(val[v][i-1],val[up[v][i-1]][i-1]);
}
for(int to:g[v]){
if(to==p)continue;
dfs(to,v);
}
tout[v]=++ti;
}
bool in(int v,int u){
return tin[v]<=tin[u]&&tout[u]<=tout[v];
}
int get_ans(int u,int v){
int ans=1e9;
for(int i=20;i>=0;i--){
if(in(u,up[v][i])==true){
ans=min(ans,val[v][i]);
v=up[v][i];
}
}
return min(ans,di[u]);
}
int lca(int v,int u){
if(in(v,u))return v;
if(in(u,v))return u;
for(int i=20;i>=0;i--)if(in(up[v][i],u)==false)v=up[v][i];
return up[v][0];
}
int ans(int v,int u){
int k=lca(u,v);
return min(get_ans(k,v),get_ans(k,u));
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<m;++i){
int u,v,c;
scanf("%d%d%d",&u,&v,&c);
g[u].push_back(v);
g[v].push_back(u);
cost[u].push_back(c);
cost[v].push_back(c);
}
int k;
scanf("%d",&k);
memset(di,63,sizeof(di));
priority_queue<pair<int,int>> q;
for(int i=1;i<=k;++i){
int l;
scanf("%d",&l);
di[l]=0;
q.push({0,l});
}
for(int i=1;i<=n;++i){
int v=-1;
while(!q.empty()){
v=q.top().second;q.pop();
if(used[v]==false){
break;
}
}
if(v==-1||used[v])break;
used[v]=true;
for(int j=0;j<g[v].size();++j){
int to=g[v][j];
int c=cost[v][j];
if(di[to]>di[v]+c){
di[to]=di[v]+c;
q.push({-di[to],to});
}
}
}
vector<pair<int,int>> ma;
for(int i=1;i<=n;++i){
ma.push_back({di[i],i});
par[i]=i;
}
sort(ma.begin(),ma.end());
vector<pair<int,int>> kox;
srand(107);
memset(used,0,sizeof(used));
for(int i=ma.size()-1;i>=0;i--){
int v=ma[i].second;
used[v]=true;
for(int to:g[v]){
if(used[to]==false)continue;
int x=fpar(v);
int y=fpar(to);
if(x!=y){
kox.push_back({v,to});
if(rand()&1){
par[x]=y;
}
else par[y]=x;
}
}
}
for(int i=0;i<=n;++i)g[i].clear();
for(pair<int,int> to:kox){
g[to.second].push_back(to.first);
g[to.first].push_back(to.second);
}
/*
for(int i=1;i<=n;++i){
cout<<di[i]<< " "<<i<<endl<<"kox:";
for(int to:g[i]){
cout<<to<<" ";
}
cout<<endl;
}
*/
dfs(1,1);
int query;
scanf("%d",&query);
for(int i=0;i<query;++i){
int u,v;
scanf("%d%d",&u,&v);
printf("%d\n",ans(u,v));
}
return 0;
}
Compilation message
plan.cpp: In function 'int main()':
plan.cpp:80:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<g[v].size();++j){
~^~~~~~~~~~~~
plan.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&m);
~~~~~^~~~~~~~~~~~~~
plan.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&u,&v,&c);
~~~~~^~~~~~~~~~~~~~~~~~~
plan.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&k);
~~~~~^~~~~~~~~
plan.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&l);
~~~~~^~~~~~~~~
plan.cpp:130:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&query);
~~~~~^~~~~~~~~~~~~
plan.cpp:133:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&u,&v);
~~~~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5468 KB |
Output is correct |
2 |
Correct |
8 ms |
5880 KB |
Output is correct |
3 |
Correct |
8 ms |
5880 KB |
Output is correct |
4 |
Correct |
6 ms |
5496 KB |
Output is correct |
5 |
Correct |
8 ms |
5904 KB |
Output is correct |
6 |
Correct |
8 ms |
5880 KB |
Output is correct |
7 |
Correct |
6 ms |
5596 KB |
Output is correct |
8 |
Correct |
6 ms |
5596 KB |
Output is correct |
9 |
Correct |
8 ms |
5880 KB |
Output is correct |
10 |
Correct |
8 ms |
5880 KB |
Output is correct |
11 |
Correct |
8 ms |
5880 KB |
Output is correct |
12 |
Correct |
8 ms |
5932 KB |
Output is correct |
13 |
Correct |
8 ms |
5880 KB |
Output is correct |
14 |
Correct |
8 ms |
5896 KB |
Output is correct |
15 |
Correct |
8 ms |
5880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5468 KB |
Output is correct |
2 |
Correct |
8 ms |
5880 KB |
Output is correct |
3 |
Correct |
8 ms |
5880 KB |
Output is correct |
4 |
Correct |
6 ms |
5496 KB |
Output is correct |
5 |
Correct |
8 ms |
5904 KB |
Output is correct |
6 |
Correct |
8 ms |
5880 KB |
Output is correct |
7 |
Correct |
6 ms |
5596 KB |
Output is correct |
8 |
Correct |
6 ms |
5596 KB |
Output is correct |
9 |
Correct |
8 ms |
5880 KB |
Output is correct |
10 |
Correct |
8 ms |
5880 KB |
Output is correct |
11 |
Correct |
8 ms |
5880 KB |
Output is correct |
12 |
Correct |
8 ms |
5932 KB |
Output is correct |
13 |
Correct |
8 ms |
5880 KB |
Output is correct |
14 |
Correct |
8 ms |
5896 KB |
Output is correct |
15 |
Correct |
8 ms |
5880 KB |
Output is correct |
16 |
Correct |
262 ms |
31860 KB |
Output is correct |
17 |
Correct |
841 ms |
49472 KB |
Output is correct |
18 |
Correct |
53 ms |
10716 KB |
Output is correct |
19 |
Correct |
254 ms |
38980 KB |
Output is correct |
20 |
Correct |
849 ms |
49996 KB |
Output is correct |
21 |
Correct |
470 ms |
40512 KB |
Output is correct |
22 |
Correct |
300 ms |
41704 KB |
Output is correct |
23 |
Correct |
818 ms |
49040 KB |
Output is correct |
24 |
Correct |
846 ms |
49072 KB |
Output is correct |
25 |
Correct |
829 ms |
49032 KB |
Output is correct |
26 |
Correct |
277 ms |
37860 KB |
Output is correct |
27 |
Correct |
286 ms |
38000 KB |
Output is correct |
28 |
Correct |
252 ms |
37812 KB |
Output is correct |
29 |
Correct |
252 ms |
38204 KB |
Output is correct |
30 |
Correct |
255 ms |
38480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5496 KB |
Output is correct |
2 |
Correct |
6 ms |
5496 KB |
Output is correct |
3 |
Correct |
6 ms |
5496 KB |
Output is correct |
4 |
Correct |
6 ms |
5496 KB |
Output is correct |
5 |
Correct |
6 ms |
5496 KB |
Output is correct |
6 |
Correct |
6 ms |
5496 KB |
Output is correct |
7 |
Correct |
6 ms |
5496 KB |
Output is correct |
8 |
Correct |
6 ms |
5496 KB |
Output is correct |
9 |
Correct |
6 ms |
5496 KB |
Output is correct |
10 |
Correct |
7 ms |
5496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
354 ms |
39452 KB |
Output is correct |
2 |
Correct |
741 ms |
47344 KB |
Output is correct |
3 |
Correct |
904 ms |
47096 KB |
Output is correct |
4 |
Correct |
221 ms |
38760 KB |
Output is correct |
5 |
Correct |
758 ms |
47132 KB |
Output is correct |
6 |
Correct |
767 ms |
47156 KB |
Output is correct |
7 |
Correct |
738 ms |
47248 KB |
Output is correct |
8 |
Correct |
732 ms |
47096 KB |
Output is correct |
9 |
Correct |
742 ms |
47192 KB |
Output is correct |
10 |
Correct |
719 ms |
47272 KB |
Output is correct |
11 |
Correct |
739 ms |
46972 KB |
Output is correct |
12 |
Correct |
775 ms |
47292 KB |
Output is correct |
13 |
Correct |
791 ms |
47212 KB |
Output is correct |
14 |
Correct |
768 ms |
47244 KB |
Output is correct |
15 |
Correct |
769 ms |
48076 KB |
Output is correct |
16 |
Correct |
714 ms |
47328 KB |
Output is correct |
17 |
Correct |
723 ms |
47300 KB |
Output is correct |
18 |
Correct |
742 ms |
47020 KB |
Output is correct |
19 |
Correct |
220 ms |
40296 KB |
Output is correct |
20 |
Correct |
744 ms |
47116 KB |
Output is correct |
21 |
Correct |
734 ms |
47056 KB |
Output is correct |
22 |
Correct |
191 ms |
37444 KB |
Output is correct |
23 |
Correct |
213 ms |
36572 KB |
Output is correct |
24 |
Correct |
184 ms |
37468 KB |
Output is correct |
25 |
Correct |
198 ms |
37348 KB |
Output is correct |
26 |
Correct |
228 ms |
37740 KB |
Output is correct |
27 |
Correct |
237 ms |
40112 KB |
Output is correct |
28 |
Correct |
194 ms |
37348 KB |
Output is correct |
29 |
Correct |
230 ms |
39436 KB |
Output is correct |
30 |
Correct |
189 ms |
37456 KB |
Output is correct |
31 |
Correct |
220 ms |
39420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5468 KB |
Output is correct |
2 |
Correct |
8 ms |
5880 KB |
Output is correct |
3 |
Correct |
8 ms |
5880 KB |
Output is correct |
4 |
Correct |
6 ms |
5496 KB |
Output is correct |
5 |
Correct |
8 ms |
5904 KB |
Output is correct |
6 |
Correct |
8 ms |
5880 KB |
Output is correct |
7 |
Correct |
6 ms |
5596 KB |
Output is correct |
8 |
Correct |
6 ms |
5596 KB |
Output is correct |
9 |
Correct |
8 ms |
5880 KB |
Output is correct |
10 |
Correct |
8 ms |
5880 KB |
Output is correct |
11 |
Correct |
8 ms |
5880 KB |
Output is correct |
12 |
Correct |
8 ms |
5932 KB |
Output is correct |
13 |
Correct |
8 ms |
5880 KB |
Output is correct |
14 |
Correct |
8 ms |
5896 KB |
Output is correct |
15 |
Correct |
8 ms |
5880 KB |
Output is correct |
16 |
Correct |
262 ms |
31860 KB |
Output is correct |
17 |
Correct |
841 ms |
49472 KB |
Output is correct |
18 |
Correct |
53 ms |
10716 KB |
Output is correct |
19 |
Correct |
254 ms |
38980 KB |
Output is correct |
20 |
Correct |
849 ms |
49996 KB |
Output is correct |
21 |
Correct |
470 ms |
40512 KB |
Output is correct |
22 |
Correct |
300 ms |
41704 KB |
Output is correct |
23 |
Correct |
818 ms |
49040 KB |
Output is correct |
24 |
Correct |
846 ms |
49072 KB |
Output is correct |
25 |
Correct |
829 ms |
49032 KB |
Output is correct |
26 |
Correct |
277 ms |
37860 KB |
Output is correct |
27 |
Correct |
286 ms |
38000 KB |
Output is correct |
28 |
Correct |
252 ms |
37812 KB |
Output is correct |
29 |
Correct |
252 ms |
38204 KB |
Output is correct |
30 |
Correct |
255 ms |
38480 KB |
Output is correct |
31 |
Correct |
6 ms |
5496 KB |
Output is correct |
32 |
Correct |
6 ms |
5496 KB |
Output is correct |
33 |
Correct |
6 ms |
5496 KB |
Output is correct |
34 |
Correct |
6 ms |
5496 KB |
Output is correct |
35 |
Correct |
6 ms |
5496 KB |
Output is correct |
36 |
Correct |
6 ms |
5496 KB |
Output is correct |
37 |
Correct |
6 ms |
5496 KB |
Output is correct |
38 |
Correct |
6 ms |
5496 KB |
Output is correct |
39 |
Correct |
6 ms |
5496 KB |
Output is correct |
40 |
Correct |
7 ms |
5496 KB |
Output is correct |
41 |
Correct |
354 ms |
39452 KB |
Output is correct |
42 |
Correct |
741 ms |
47344 KB |
Output is correct |
43 |
Correct |
904 ms |
47096 KB |
Output is correct |
44 |
Correct |
221 ms |
38760 KB |
Output is correct |
45 |
Correct |
758 ms |
47132 KB |
Output is correct |
46 |
Correct |
767 ms |
47156 KB |
Output is correct |
47 |
Correct |
738 ms |
47248 KB |
Output is correct |
48 |
Correct |
732 ms |
47096 KB |
Output is correct |
49 |
Correct |
742 ms |
47192 KB |
Output is correct |
50 |
Correct |
719 ms |
47272 KB |
Output is correct |
51 |
Correct |
739 ms |
46972 KB |
Output is correct |
52 |
Correct |
775 ms |
47292 KB |
Output is correct |
53 |
Correct |
791 ms |
47212 KB |
Output is correct |
54 |
Correct |
768 ms |
47244 KB |
Output is correct |
55 |
Correct |
769 ms |
48076 KB |
Output is correct |
56 |
Correct |
714 ms |
47328 KB |
Output is correct |
57 |
Correct |
723 ms |
47300 KB |
Output is correct |
58 |
Correct |
742 ms |
47020 KB |
Output is correct |
59 |
Correct |
220 ms |
40296 KB |
Output is correct |
60 |
Correct |
744 ms |
47116 KB |
Output is correct |
61 |
Correct |
734 ms |
47056 KB |
Output is correct |
62 |
Correct |
191 ms |
37444 KB |
Output is correct |
63 |
Correct |
213 ms |
36572 KB |
Output is correct |
64 |
Correct |
184 ms |
37468 KB |
Output is correct |
65 |
Correct |
198 ms |
37348 KB |
Output is correct |
66 |
Correct |
228 ms |
37740 KB |
Output is correct |
67 |
Correct |
237 ms |
40112 KB |
Output is correct |
68 |
Correct |
194 ms |
37348 KB |
Output is correct |
69 |
Correct |
230 ms |
39436 KB |
Output is correct |
70 |
Correct |
189 ms |
37456 KB |
Output is correct |
71 |
Correct |
220 ms |
39420 KB |
Output is correct |
72 |
Correct |
491 ms |
39848 KB |
Output is correct |
73 |
Correct |
844 ms |
47324 KB |
Output is correct |
74 |
Correct |
853 ms |
47700 KB |
Output is correct |
75 |
Correct |
862 ms |
47648 KB |
Output is correct |
76 |
Correct |
866 ms |
47244 KB |
Output is correct |
77 |
Correct |
865 ms |
47096 KB |
Output is correct |
78 |
Correct |
845 ms |
46568 KB |
Output is correct |
79 |
Correct |
866 ms |
46036 KB |
Output is correct |
80 |
Correct |
843 ms |
46180 KB |
Output is correct |
81 |
Correct |
908 ms |
46080 KB |
Output is correct |
82 |
Correct |
838 ms |
46172 KB |
Output is correct |
83 |
Correct |
820 ms |
45996 KB |
Output is correct |
84 |
Correct |
795 ms |
46036 KB |
Output is correct |
85 |
Correct |
845 ms |
46952 KB |
Output is correct |
86 |
Correct |
873 ms |
46000 KB |
Output is correct |
87 |
Correct |
829 ms |
45972 KB |
Output is correct |
88 |
Correct |
865 ms |
46004 KB |
Output is correct |
89 |
Correct |
345 ms |
39660 KB |
Output is correct |
90 |
Correct |
835 ms |
45984 KB |
Output is correct |
91 |
Correct |
808 ms |
45496 KB |
Output is correct |
92 |
Correct |
270 ms |
36960 KB |
Output is correct |
93 |
Correct |
361 ms |
36592 KB |
Output is correct |
94 |
Correct |
279 ms |
36836 KB |
Output is correct |
95 |
Correct |
278 ms |
36908 KB |
Output is correct |
96 |
Correct |
351 ms |
37216 KB |
Output is correct |
97 |
Correct |
367 ms |
38688 KB |
Output is correct |
98 |
Correct |
279 ms |
36928 KB |
Output is correct |
99 |
Correct |
388 ms |
39916 KB |
Output is correct |
100 |
Correct |
273 ms |
36652 KB |
Output is correct |