#include <bits/stdc++.h>
#define pb push_back
#define ss second
#define ff first
#define N 100005
#define inf 1000000009
#define ll long long
#define mid(a,b) (a+b)/2
#define pii pair<int,int>
using namespace std;
int n,m,w,k,t,dis[N],ans,x,y,L[N],sp[N][22],vis[N],mn[N][22],par[N];
priority_queue <pii,vector <pii>,greater<pii>> q;
vector <pii> E[N];
vector <int> EG[N];
vector <pair<int,pii>> adj;
int ata(int x){
if(x == par[x]) return x;
return par[x] = ata(par[x]);
}
bool isS(int x,int y){
x = ata(x),y = ata(y);
if(x == y) return 1;
return 0;
}
void un(int x,int y){
x = ata(x),y = ata(y);
par[y] = x;
}
void sol(){
for(auto i : adj){
w = i.ff,x = i.ss.ff,y = i.ss.ss;
if(!isS(x,y)){
EG[y].pb(x);
EG[x].pb(y);
un(x,y);
}
}
}
void dfs(int nd,int pr){
L[nd] = L[pr] + 1;
sp[nd][0] = pr;
mn[nd][0] = min(dis[nd],dis[pr]);
for(auto i : EG[nd]){
if(i != pr){
dfs(i,nd);
}
}
}
void LCA(int x,int y){
ans = min(dis[x],dis[y]);
if(L[x] < L[y]) swap(x,y);
for(int i = 20;i >= 0;i--){
if(L[sp[x][i]] >= L[y] and sp[x][i]){
ans = min(mn[x][i],ans);
x = sp[x][i];
}
}
if(x == y) return;
for(int i = 20;i >= 0;i--)
if(sp[x][i] != sp[y][i] and sp[x][i] and sp[y][i]){
ans = min(ans,min(mn[y][i],mn[x][i]));
x = sp[x][i],y = sp[y][i];
}
ans = min(ans,dis[sp[x][0]]);
return;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1;i <= m;i++){
scanf("%d%d%d",&x,&y,&w);
adj.pb({0,{x,y}});
E[x].pb({y,w});
E[y].pb({x,w});
}
for(int i = 0;i <= n;i++){
dis[i] = mn[i][0] = inf;
par[i] = i;
}
scanf("%d",&k);
for(int i = 1;i <= k;i++){
scanf("%d",&x);
dis[x] = 0;
q.push({0,x});
}
while(!q.empty()){
x = q.top().ss;
q.pop();
if(vis[x]) continue;
vis[x] = 1;
for(auto i : E[x]){
if(dis[i.ff] > dis[x] + i.ss){
dis[i.ff] = dis[x] + i.ss;
q.push({dis[i.ff],i.ff});
}
}
}
for(int i = 0;i < adj.size();i++)
adj[i].ff = min(dis[adj[i].ss.ff],dis[adj[i].ss.ss]);
sort(adj.begin(),adj.end());
reverse(adj.begin(),adj.end());
sol();
dfs(1,0);
int lg = log2(n);
for(int i = 1;i <= lg;i++){
for(int j = 1;j <= n;j++){
sp[j][i] = sp[sp[j][i - 1]][i - 1];
mn[j][i] = min(mn[j][i - 1],mn[sp[j][i - 1]][i - 1]);
}
}
scanf("%d",&t);
while(t--){
scanf("%d%d",&x,&y);
LCA(x,y);
printf("%d\n",ans);
}
}
/*
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
*/
Compilation message
plan.cpp: In function 'int main()':
plan.cpp:112:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < adj.size();i++)
~~^~~~~~~~~~~~
plan.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&m);
~~~~~^~~~~~~~~~~~~~
plan.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&x,&y,&w);
~~~~~^~~~~~~~~~~~~~~~~~~
plan.cpp:94:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&k);
~~~~~^~~~~~~~~
plan.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&x);
~~~~~^~~~~~~~~
plan.cpp:125:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&t);
~~~~~^~~~~~~~~
plan.cpp:127:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&x,&y);
~~~~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
4980 KB |
Output is correct |
2 |
Correct |
9 ms |
5368 KB |
Output is correct |
3 |
Correct |
9 ms |
5368 KB |
Output is correct |
4 |
Correct |
8 ms |
4984 KB |
Output is correct |
5 |
Correct |
9 ms |
5368 KB |
Output is correct |
6 |
Correct |
9 ms |
5368 KB |
Output is correct |
7 |
Correct |
8 ms |
5112 KB |
Output is correct |
8 |
Correct |
8 ms |
5112 KB |
Output is correct |
9 |
Correct |
9 ms |
5368 KB |
Output is correct |
10 |
Correct |
10 ms |
5368 KB |
Output is correct |
11 |
Correct |
9 ms |
5368 KB |
Output is correct |
12 |
Correct |
9 ms |
5368 KB |
Output is correct |
13 |
Correct |
9 ms |
5368 KB |
Output is correct |
14 |
Correct |
9 ms |
5368 KB |
Output is correct |
15 |
Correct |
9 ms |
5368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
4980 KB |
Output is correct |
2 |
Correct |
9 ms |
5368 KB |
Output is correct |
3 |
Correct |
9 ms |
5368 KB |
Output is correct |
4 |
Correct |
8 ms |
4984 KB |
Output is correct |
5 |
Correct |
9 ms |
5368 KB |
Output is correct |
6 |
Correct |
9 ms |
5368 KB |
Output is correct |
7 |
Correct |
8 ms |
5112 KB |
Output is correct |
8 |
Correct |
8 ms |
5112 KB |
Output is correct |
9 |
Correct |
9 ms |
5368 KB |
Output is correct |
10 |
Correct |
10 ms |
5368 KB |
Output is correct |
11 |
Correct |
9 ms |
5368 KB |
Output is correct |
12 |
Correct |
9 ms |
5368 KB |
Output is correct |
13 |
Correct |
9 ms |
5368 KB |
Output is correct |
14 |
Correct |
9 ms |
5368 KB |
Output is correct |
15 |
Correct |
9 ms |
5368 KB |
Output is correct |
16 |
Correct |
269 ms |
30120 KB |
Output is correct |
17 |
Correct |
763 ms |
56368 KB |
Output is correct |
18 |
Correct |
51 ms |
10160 KB |
Output is correct |
19 |
Correct |
231 ms |
36508 KB |
Output is correct |
20 |
Correct |
788 ms |
56472 KB |
Output is correct |
21 |
Correct |
420 ms |
40740 KB |
Output is correct |
22 |
Correct |
257 ms |
39720 KB |
Output is correct |
23 |
Correct |
768 ms |
56216 KB |
Output is correct |
24 |
Correct |
782 ms |
56348 KB |
Output is correct |
25 |
Correct |
773 ms |
56472 KB |
Output is correct |
26 |
Correct |
223 ms |
36380 KB |
Output is correct |
27 |
Correct |
224 ms |
36504 KB |
Output is correct |
28 |
Correct |
225 ms |
36256 KB |
Output is correct |
29 |
Correct |
221 ms |
36696 KB |
Output is correct |
30 |
Correct |
241 ms |
36640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
4984 KB |
Output is correct |
2 |
Correct |
8 ms |
4984 KB |
Output is correct |
3 |
Correct |
8 ms |
5112 KB |
Output is correct |
4 |
Correct |
8 ms |
4984 KB |
Output is correct |
5 |
Correct |
7 ms |
5112 KB |
Output is correct |
6 |
Correct |
9 ms |
5112 KB |
Output is correct |
7 |
Correct |
8 ms |
4984 KB |
Output is correct |
8 |
Correct |
8 ms |
4984 KB |
Output is correct |
9 |
Correct |
8 ms |
4988 KB |
Output is correct |
10 |
Correct |
8 ms |
4984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
354 ms |
38688 KB |
Output is correct |
2 |
Correct |
663 ms |
49432 KB |
Output is correct |
3 |
Correct |
650 ms |
49436 KB |
Output is correct |
4 |
Correct |
183 ms |
35888 KB |
Output is correct |
5 |
Correct |
663 ms |
49336 KB |
Output is correct |
6 |
Correct |
669 ms |
49432 KB |
Output is correct |
7 |
Correct |
662 ms |
49400 KB |
Output is correct |
8 |
Correct |
671 ms |
49548 KB |
Output is correct |
9 |
Correct |
667 ms |
49432 KB |
Output is correct |
10 |
Correct |
654 ms |
49432 KB |
Output is correct |
11 |
Correct |
666 ms |
49568 KB |
Output is correct |
12 |
Correct |
672 ms |
49564 KB |
Output is correct |
13 |
Correct |
654 ms |
49532 KB |
Output is correct |
14 |
Correct |
684 ms |
49560 KB |
Output is correct |
15 |
Correct |
677 ms |
49820 KB |
Output is correct |
16 |
Correct |
665 ms |
49316 KB |
Output is correct |
17 |
Correct |
659 ms |
49432 KB |
Output is correct |
18 |
Correct |
666 ms |
49420 KB |
Output is correct |
19 |
Correct |
177 ms |
37292 KB |
Output is correct |
20 |
Correct |
661 ms |
49304 KB |
Output is correct |
21 |
Correct |
628 ms |
49048 KB |
Output is correct |
22 |
Correct |
160 ms |
34852 KB |
Output is correct |
23 |
Correct |
172 ms |
33960 KB |
Output is correct |
24 |
Correct |
158 ms |
34848 KB |
Output is correct |
25 |
Correct |
154 ms |
34848 KB |
Output is correct |
26 |
Correct |
193 ms |
34476 KB |
Output is correct |
27 |
Correct |
190 ms |
37300 KB |
Output is correct |
28 |
Correct |
154 ms |
34840 KB |
Output is correct |
29 |
Correct |
181 ms |
36396 KB |
Output is correct |
30 |
Correct |
160 ms |
34996 KB |
Output is correct |
31 |
Correct |
191 ms |
36524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
4980 KB |
Output is correct |
2 |
Correct |
9 ms |
5368 KB |
Output is correct |
3 |
Correct |
9 ms |
5368 KB |
Output is correct |
4 |
Correct |
8 ms |
4984 KB |
Output is correct |
5 |
Correct |
9 ms |
5368 KB |
Output is correct |
6 |
Correct |
9 ms |
5368 KB |
Output is correct |
7 |
Correct |
8 ms |
5112 KB |
Output is correct |
8 |
Correct |
8 ms |
5112 KB |
Output is correct |
9 |
Correct |
9 ms |
5368 KB |
Output is correct |
10 |
Correct |
10 ms |
5368 KB |
Output is correct |
11 |
Correct |
9 ms |
5368 KB |
Output is correct |
12 |
Correct |
9 ms |
5368 KB |
Output is correct |
13 |
Correct |
9 ms |
5368 KB |
Output is correct |
14 |
Correct |
9 ms |
5368 KB |
Output is correct |
15 |
Correct |
9 ms |
5368 KB |
Output is correct |
16 |
Correct |
269 ms |
30120 KB |
Output is correct |
17 |
Correct |
763 ms |
56368 KB |
Output is correct |
18 |
Correct |
51 ms |
10160 KB |
Output is correct |
19 |
Correct |
231 ms |
36508 KB |
Output is correct |
20 |
Correct |
788 ms |
56472 KB |
Output is correct |
21 |
Correct |
420 ms |
40740 KB |
Output is correct |
22 |
Correct |
257 ms |
39720 KB |
Output is correct |
23 |
Correct |
768 ms |
56216 KB |
Output is correct |
24 |
Correct |
782 ms |
56348 KB |
Output is correct |
25 |
Correct |
773 ms |
56472 KB |
Output is correct |
26 |
Correct |
223 ms |
36380 KB |
Output is correct |
27 |
Correct |
224 ms |
36504 KB |
Output is correct |
28 |
Correct |
225 ms |
36256 KB |
Output is correct |
29 |
Correct |
221 ms |
36696 KB |
Output is correct |
30 |
Correct |
241 ms |
36640 KB |
Output is correct |
31 |
Correct |
8 ms |
4984 KB |
Output is correct |
32 |
Correct |
8 ms |
4984 KB |
Output is correct |
33 |
Correct |
8 ms |
5112 KB |
Output is correct |
34 |
Correct |
8 ms |
4984 KB |
Output is correct |
35 |
Correct |
7 ms |
5112 KB |
Output is correct |
36 |
Correct |
9 ms |
5112 KB |
Output is correct |
37 |
Correct |
8 ms |
4984 KB |
Output is correct |
38 |
Correct |
8 ms |
4984 KB |
Output is correct |
39 |
Correct |
8 ms |
4988 KB |
Output is correct |
40 |
Correct |
8 ms |
4984 KB |
Output is correct |
41 |
Correct |
354 ms |
38688 KB |
Output is correct |
42 |
Correct |
663 ms |
49432 KB |
Output is correct |
43 |
Correct |
650 ms |
49436 KB |
Output is correct |
44 |
Correct |
183 ms |
35888 KB |
Output is correct |
45 |
Correct |
663 ms |
49336 KB |
Output is correct |
46 |
Correct |
669 ms |
49432 KB |
Output is correct |
47 |
Correct |
662 ms |
49400 KB |
Output is correct |
48 |
Correct |
671 ms |
49548 KB |
Output is correct |
49 |
Correct |
667 ms |
49432 KB |
Output is correct |
50 |
Correct |
654 ms |
49432 KB |
Output is correct |
51 |
Correct |
666 ms |
49568 KB |
Output is correct |
52 |
Correct |
672 ms |
49564 KB |
Output is correct |
53 |
Correct |
654 ms |
49532 KB |
Output is correct |
54 |
Correct |
684 ms |
49560 KB |
Output is correct |
55 |
Correct |
677 ms |
49820 KB |
Output is correct |
56 |
Correct |
665 ms |
49316 KB |
Output is correct |
57 |
Correct |
659 ms |
49432 KB |
Output is correct |
58 |
Correct |
666 ms |
49420 KB |
Output is correct |
59 |
Correct |
177 ms |
37292 KB |
Output is correct |
60 |
Correct |
661 ms |
49304 KB |
Output is correct |
61 |
Correct |
628 ms |
49048 KB |
Output is correct |
62 |
Correct |
160 ms |
34852 KB |
Output is correct |
63 |
Correct |
172 ms |
33960 KB |
Output is correct |
64 |
Correct |
158 ms |
34848 KB |
Output is correct |
65 |
Correct |
154 ms |
34848 KB |
Output is correct |
66 |
Correct |
193 ms |
34476 KB |
Output is correct |
67 |
Correct |
190 ms |
37300 KB |
Output is correct |
68 |
Correct |
154 ms |
34840 KB |
Output is correct |
69 |
Correct |
181 ms |
36396 KB |
Output is correct |
70 |
Correct |
160 ms |
34996 KB |
Output is correct |
71 |
Correct |
191 ms |
36524 KB |
Output is correct |
72 |
Correct |
462 ms |
40612 KB |
Output is correct |
73 |
Correct |
797 ms |
56344 KB |
Output is correct |
74 |
Correct |
802 ms |
56220 KB |
Output is correct |
75 |
Correct |
808 ms |
56476 KB |
Output is correct |
76 |
Correct |
799 ms |
56384 KB |
Output is correct |
77 |
Correct |
786 ms |
56284 KB |
Output is correct |
78 |
Correct |
810 ms |
56352 KB |
Output is correct |
79 |
Correct |
787 ms |
56220 KB |
Output is correct |
80 |
Correct |
798 ms |
56232 KB |
Output is correct |
81 |
Correct |
773 ms |
56192 KB |
Output is correct |
82 |
Correct |
777 ms |
56272 KB |
Output is correct |
83 |
Correct |
782 ms |
56376 KB |
Output is correct |
84 |
Correct |
803 ms |
56216 KB |
Output is correct |
85 |
Correct |
773 ms |
56672 KB |
Output is correct |
86 |
Correct |
778 ms |
56476 KB |
Output is correct |
87 |
Correct |
773 ms |
56348 KB |
Output is correct |
88 |
Correct |
776 ms |
56384 KB |
Output is correct |
89 |
Correct |
363 ms |
38696 KB |
Output is correct |
90 |
Correct |
777 ms |
56408 KB |
Output is correct |
91 |
Correct |
742 ms |
56368 KB |
Output is correct |
92 |
Correct |
220 ms |
36384 KB |
Output is correct |
93 |
Correct |
316 ms |
36028 KB |
Output is correct |
94 |
Correct |
227 ms |
36380 KB |
Output is correct |
95 |
Correct |
225 ms |
36376 KB |
Output is correct |
96 |
Correct |
338 ms |
35624 KB |
Output is correct |
97 |
Correct |
373 ms |
37804 KB |
Output is correct |
98 |
Correct |
231 ms |
36384 KB |
Output is correct |
99 |
Correct |
358 ms |
38952 KB |
Output is correct |
100 |
Correct |
229 ms |
36512 KB |
Output is correct |