#include <bits/stdc++.h>
using namespace std;
vector<int> g[100007],gt[100007],c[100007],z;
int d[100007],arr[100007],dsu[100007],p[20][100007],in[100007],out[100007],n,ti,l[20][100007];
bool vi[100007];
int root(int u)
{
while(dsu[u]!=u)
{
dsu[u]=dsu[dsu[u]];
u=dsu[u];
}
return u;
}
bool cmp(int a,int b) {return d[a]>d[b];}
void simuldij()
{
priority_queue<pair<int,int> > pq;
for(int i=0;i<z.size();i++) pq.push(make_pair(0,z[i]));
while(!pq.empty())
{
int s=pq.top().second,a=-pq.top().first;
pq.pop();
if(vi[s]) continue;
vi[s]=true;
d[s]=a;
for(int i=0;i<g[s].size();i++) pq.push(make_pair(-a-c[s][i],g[s][i]));
}
}
void dfs(int s,int f)
{
p[0][s]=f;
l[0][s]=d[s];
in[s]=ti++;
for(int i=0;i<gt[s].size();i++) dfs(gt[s][i],s);
out[s]=ti++;
}
void lcainit()
{
dfs(arr[n],0);
in[0]=-1;
out[0]=1000000000;
l[0][0]=2000000000;
d[0]=2000000000;
for(int i=1;i<20;i++) for(int j=1;j<=n;j++) {l[i][j]=min(l[i-1][j],l[i-1][p[i-1][j]]); p[i][j]=p[i-1][p[i-1][j]];}
}
bool insub(int a,int b) {return in[a]>=in[b] && out[a]<=out[b];}
int query(int a,int b)
{
int x=a,y=b,sol=2000000000;
for(int i=19;i>=0;i--) if(!insub(b,p[i][x])) {sol=min(sol,l[i][x]); x=p[i][x];}
sol=min(sol,d[x]);
if(!insub(b,a)) sol=min(sol,d[p[0][x]]);
for(int i=19;i>=0;i--) if(!insub(a,p[i][y])) {sol=min(sol,l[i][y]); y=p[i][y];}
sol=min(sol,d[y]);
if(!insub(a,b)) sol=min(sol,d[p[0][y]]);
return sol;
}
int main()
{
int m,za,q,t;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
{
int t1,t2,t3;
scanf("%d%d%d",&t1,&t2,&t3);
g[t1].push_back(t2);
g[t2].push_back(t1);
c[t1].push_back(t3);
c[t2].push_back(t3);
}
scanf("%d",&za);
for(int i=0;i<za;i++) {scanf("%d",&t); z.push_back(t);}
simuldij();
for(int i=1;i<=n;i++) arr[i]=dsu[i]=i;
fill(vi,vi+n+1,false);
sort(arr+1,arr+n+1,cmp);
for(int i=1;i<=n;i++)
{
vi[arr[i]]=true;
for(int j=0;j<g[arr[i]].size();j++) if(vi[g[arr[i]][j]] && root(g[arr[i]][j])!=arr[i]) {gt[arr[i]].push_back(root(g[arr[i]][j])); dsu[root(g[arr[i]][j])]=arr[i];}
}
lcainit();
scanf("%d",&q);
for(int i=0;i<q;i++)
{
int t1,t2;
scanf("%d%d",&t1,&t2);
printf("%d\n",query(t1,t2));
}
}
Compilation message
plan.cpp: In function 'void simuldij()':
plan.cpp:19:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<z.size();i++) pq.push(make_pair(0,z[i]));
~^~~~~~~~~
plan.cpp:27:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[s].size();i++) pq.push(make_pair(-a-c[s][i],g[s][i]));
~^~~~~~~~~~~~
plan.cpp: In function 'void dfs(int, int)':
plan.cpp:35:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<gt[s].size();i++) dfs(gt[s][i],s);
~^~~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:81:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<g[arr[i]].size();j++) if(vi[g[arr[i]][j]] && root(g[arr[i]][j])!=arr[i]) {gt[arr[i]].push_back(root(g[arr[i]][j])); dsu[root(g[arr[i]][j])]=arr[i];}
~^~~~~~~~~~~~~~~~~
plan.cpp:62: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:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&t1,&t2,&t3);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&za);
~~~~~^~~~~~~~~~
plan.cpp:73:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=0;i<za;i++) {scanf("%d",&t); z.push_back(t);}
~~~~~^~~~~~~~~
plan.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&q);
~~~~~^~~~~~~~~
plan.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&t1,&t2);
~~~~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
7544 KB |
Output is correct |
2 |
Correct |
10 ms |
7800 KB |
Output is correct |
3 |
Correct |
10 ms |
7932 KB |
Output is correct |
4 |
Correct |
8 ms |
7548 KB |
Output is correct |
5 |
Correct |
10 ms |
7800 KB |
Output is correct |
6 |
Correct |
10 ms |
7928 KB |
Output is correct |
7 |
Correct |
8 ms |
7544 KB |
Output is correct |
8 |
Correct |
8 ms |
7544 KB |
Output is correct |
9 |
Correct |
10 ms |
7928 KB |
Output is correct |
10 |
Correct |
10 ms |
7800 KB |
Output is correct |
11 |
Correct |
10 ms |
7800 KB |
Output is correct |
12 |
Correct |
9 ms |
7800 KB |
Output is correct |
13 |
Correct |
10 ms |
7928 KB |
Output is correct |
14 |
Correct |
10 ms |
7804 KB |
Output is correct |
15 |
Correct |
10 ms |
7800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
7544 KB |
Output is correct |
2 |
Correct |
10 ms |
7800 KB |
Output is correct |
3 |
Correct |
10 ms |
7932 KB |
Output is correct |
4 |
Correct |
8 ms |
7548 KB |
Output is correct |
5 |
Correct |
10 ms |
7800 KB |
Output is correct |
6 |
Correct |
10 ms |
7928 KB |
Output is correct |
7 |
Correct |
8 ms |
7544 KB |
Output is correct |
8 |
Correct |
8 ms |
7544 KB |
Output is correct |
9 |
Correct |
10 ms |
7928 KB |
Output is correct |
10 |
Correct |
10 ms |
7800 KB |
Output is correct |
11 |
Correct |
10 ms |
7800 KB |
Output is correct |
12 |
Correct |
9 ms |
7800 KB |
Output is correct |
13 |
Correct |
10 ms |
7928 KB |
Output is correct |
14 |
Correct |
10 ms |
7804 KB |
Output is correct |
15 |
Correct |
10 ms |
7800 KB |
Output is correct |
16 |
Correct |
315 ms |
30152 KB |
Output is correct |
17 |
Correct |
1146 ms |
47504 KB |
Output is correct |
18 |
Correct |
68 ms |
12148 KB |
Output is correct |
19 |
Correct |
264 ms |
33888 KB |
Output is correct |
20 |
Correct |
1145 ms |
47004 KB |
Output is correct |
21 |
Correct |
565 ms |
38312 KB |
Output is correct |
22 |
Correct |
272 ms |
40056 KB |
Output is correct |
23 |
Correct |
1162 ms |
46964 KB |
Output is correct |
24 |
Correct |
1172 ms |
47028 KB |
Output is correct |
25 |
Correct |
1207 ms |
47004 KB |
Output is correct |
26 |
Correct |
262 ms |
34540 KB |
Output is correct |
27 |
Correct |
245 ms |
34772 KB |
Output is correct |
28 |
Correct |
242 ms |
34380 KB |
Output is correct |
29 |
Correct |
249 ms |
34520 KB |
Output is correct |
30 |
Correct |
253 ms |
35080 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
7544 KB |
Output is correct |
2 |
Correct |
10 ms |
7544 KB |
Output is correct |
3 |
Correct |
8 ms |
7544 KB |
Output is correct |
4 |
Correct |
8 ms |
7544 KB |
Output is correct |
5 |
Correct |
8 ms |
7544 KB |
Output is correct |
6 |
Correct |
8 ms |
7672 KB |
Output is correct |
7 |
Correct |
8 ms |
7544 KB |
Output is correct |
8 |
Correct |
8 ms |
7544 KB |
Output is correct |
9 |
Correct |
8 ms |
7624 KB |
Output is correct |
10 |
Correct |
8 ms |
7544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
407 ms |
38528 KB |
Output is correct |
2 |
Correct |
959 ms |
48320 KB |
Output is correct |
3 |
Correct |
967 ms |
48116 KB |
Output is correct |
4 |
Correct |
191 ms |
37268 KB |
Output is correct |
5 |
Correct |
944 ms |
48332 KB |
Output is correct |
6 |
Correct |
937 ms |
48324 KB |
Output is correct |
7 |
Correct |
930 ms |
47984 KB |
Output is correct |
8 |
Correct |
932 ms |
48144 KB |
Output is correct |
9 |
Correct |
945 ms |
48648 KB |
Output is correct |
10 |
Correct |
940 ms |
48252 KB |
Output is correct |
11 |
Correct |
1053 ms |
48192 KB |
Output is correct |
12 |
Correct |
987 ms |
47532 KB |
Output is correct |
13 |
Correct |
1006 ms |
47472 KB |
Output is correct |
14 |
Correct |
980 ms |
47312 KB |
Output is correct |
15 |
Correct |
1076 ms |
47756 KB |
Output is correct |
16 |
Correct |
945 ms |
47828 KB |
Output is correct |
17 |
Correct |
970 ms |
47648 KB |
Output is correct |
18 |
Correct |
966 ms |
47520 KB |
Output is correct |
19 |
Correct |
202 ms |
39288 KB |
Output is correct |
20 |
Correct |
978 ms |
47632 KB |
Output is correct |
21 |
Correct |
929 ms |
48292 KB |
Output is correct |
22 |
Correct |
181 ms |
33528 KB |
Output is correct |
23 |
Correct |
206 ms |
35004 KB |
Output is correct |
24 |
Correct |
185 ms |
33452 KB |
Output is correct |
25 |
Correct |
207 ms |
33656 KB |
Output is correct |
26 |
Correct |
211 ms |
34360 KB |
Output is correct |
27 |
Correct |
192 ms |
37368 KB |
Output is correct |
28 |
Correct |
180 ms |
33492 KB |
Output is correct |
29 |
Correct |
198 ms |
37496 KB |
Output is correct |
30 |
Correct |
181 ms |
33608 KB |
Output is correct |
31 |
Correct |
198 ms |
37196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
7544 KB |
Output is correct |
2 |
Correct |
10 ms |
7800 KB |
Output is correct |
3 |
Correct |
10 ms |
7932 KB |
Output is correct |
4 |
Correct |
8 ms |
7548 KB |
Output is correct |
5 |
Correct |
10 ms |
7800 KB |
Output is correct |
6 |
Correct |
10 ms |
7928 KB |
Output is correct |
7 |
Correct |
8 ms |
7544 KB |
Output is correct |
8 |
Correct |
8 ms |
7544 KB |
Output is correct |
9 |
Correct |
10 ms |
7928 KB |
Output is correct |
10 |
Correct |
10 ms |
7800 KB |
Output is correct |
11 |
Correct |
10 ms |
7800 KB |
Output is correct |
12 |
Correct |
9 ms |
7800 KB |
Output is correct |
13 |
Correct |
10 ms |
7928 KB |
Output is correct |
14 |
Correct |
10 ms |
7804 KB |
Output is correct |
15 |
Correct |
10 ms |
7800 KB |
Output is correct |
16 |
Correct |
315 ms |
30152 KB |
Output is correct |
17 |
Correct |
1146 ms |
47504 KB |
Output is correct |
18 |
Correct |
68 ms |
12148 KB |
Output is correct |
19 |
Correct |
264 ms |
33888 KB |
Output is correct |
20 |
Correct |
1145 ms |
47004 KB |
Output is correct |
21 |
Correct |
565 ms |
38312 KB |
Output is correct |
22 |
Correct |
272 ms |
40056 KB |
Output is correct |
23 |
Correct |
1162 ms |
46964 KB |
Output is correct |
24 |
Correct |
1172 ms |
47028 KB |
Output is correct |
25 |
Correct |
1207 ms |
47004 KB |
Output is correct |
26 |
Correct |
262 ms |
34540 KB |
Output is correct |
27 |
Correct |
245 ms |
34772 KB |
Output is correct |
28 |
Correct |
242 ms |
34380 KB |
Output is correct |
29 |
Correct |
249 ms |
34520 KB |
Output is correct |
30 |
Correct |
253 ms |
35080 KB |
Output is correct |
31 |
Correct |
8 ms |
7544 KB |
Output is correct |
32 |
Correct |
10 ms |
7544 KB |
Output is correct |
33 |
Correct |
8 ms |
7544 KB |
Output is correct |
34 |
Correct |
8 ms |
7544 KB |
Output is correct |
35 |
Correct |
8 ms |
7544 KB |
Output is correct |
36 |
Correct |
8 ms |
7672 KB |
Output is correct |
37 |
Correct |
8 ms |
7544 KB |
Output is correct |
38 |
Correct |
8 ms |
7544 KB |
Output is correct |
39 |
Correct |
8 ms |
7624 KB |
Output is correct |
40 |
Correct |
8 ms |
7544 KB |
Output is correct |
41 |
Correct |
407 ms |
38528 KB |
Output is correct |
42 |
Correct |
959 ms |
48320 KB |
Output is correct |
43 |
Correct |
967 ms |
48116 KB |
Output is correct |
44 |
Correct |
191 ms |
37268 KB |
Output is correct |
45 |
Correct |
944 ms |
48332 KB |
Output is correct |
46 |
Correct |
937 ms |
48324 KB |
Output is correct |
47 |
Correct |
930 ms |
47984 KB |
Output is correct |
48 |
Correct |
932 ms |
48144 KB |
Output is correct |
49 |
Correct |
945 ms |
48648 KB |
Output is correct |
50 |
Correct |
940 ms |
48252 KB |
Output is correct |
51 |
Correct |
1053 ms |
48192 KB |
Output is correct |
52 |
Correct |
987 ms |
47532 KB |
Output is correct |
53 |
Correct |
1006 ms |
47472 KB |
Output is correct |
54 |
Correct |
980 ms |
47312 KB |
Output is correct |
55 |
Correct |
1076 ms |
47756 KB |
Output is correct |
56 |
Correct |
945 ms |
47828 KB |
Output is correct |
57 |
Correct |
970 ms |
47648 KB |
Output is correct |
58 |
Correct |
966 ms |
47520 KB |
Output is correct |
59 |
Correct |
202 ms |
39288 KB |
Output is correct |
60 |
Correct |
978 ms |
47632 KB |
Output is correct |
61 |
Correct |
929 ms |
48292 KB |
Output is correct |
62 |
Correct |
181 ms |
33528 KB |
Output is correct |
63 |
Correct |
206 ms |
35004 KB |
Output is correct |
64 |
Correct |
185 ms |
33452 KB |
Output is correct |
65 |
Correct |
207 ms |
33656 KB |
Output is correct |
66 |
Correct |
211 ms |
34360 KB |
Output is correct |
67 |
Correct |
192 ms |
37368 KB |
Output is correct |
68 |
Correct |
180 ms |
33492 KB |
Output is correct |
69 |
Correct |
198 ms |
37496 KB |
Output is correct |
70 |
Correct |
181 ms |
33608 KB |
Output is correct |
71 |
Correct |
198 ms |
37196 KB |
Output is correct |
72 |
Correct |
563 ms |
39492 KB |
Output is correct |
73 |
Correct |
1111 ms |
48212 KB |
Output is correct |
74 |
Correct |
1243 ms |
48480 KB |
Output is correct |
75 |
Correct |
1119 ms |
48184 KB |
Output is correct |
76 |
Correct |
1097 ms |
48532 KB |
Output is correct |
77 |
Correct |
1133 ms |
48348 KB |
Output is correct |
78 |
Correct |
1091 ms |
48376 KB |
Output is correct |
79 |
Correct |
1117 ms |
48224 KB |
Output is correct |
80 |
Correct |
1173 ms |
48332 KB |
Output is correct |
81 |
Correct |
1153 ms |
48648 KB |
Output is correct |
82 |
Correct |
1154 ms |
47980 KB |
Output is correct |
83 |
Correct |
1106 ms |
47968 KB |
Output is correct |
84 |
Correct |
1133 ms |
48172 KB |
Output is correct |
85 |
Correct |
1125 ms |
48260 KB |
Output is correct |
86 |
Correct |
1172 ms |
48444 KB |
Output is correct |
87 |
Correct |
1141 ms |
47904 KB |
Output is correct |
88 |
Correct |
1132 ms |
50112 KB |
Output is correct |
89 |
Correct |
350 ms |
40880 KB |
Output is correct |
90 |
Correct |
1144 ms |
48960 KB |
Output is correct |
91 |
Correct |
1091 ms |
48748 KB |
Output is correct |
92 |
Correct |
270 ms |
34100 KB |
Output is correct |
93 |
Correct |
345 ms |
35924 KB |
Output is correct |
94 |
Correct |
261 ms |
34144 KB |
Output is correct |
95 |
Correct |
274 ms |
34316 KB |
Output is correct |
96 |
Correct |
319 ms |
35032 KB |
Output is correct |
97 |
Correct |
383 ms |
38500 KB |
Output is correct |
98 |
Correct |
259 ms |
34600 KB |
Output is correct |
99 |
Correct |
373 ms |
38424 KB |
Output is correct |
100 |
Correct |
271 ms |
34376 KB |
Output is correct |