#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
vector < pair < int , int > > Next[200005];
vector < pair < int , int > > Next2[200005];
pair < int , int > Father[30][200005];
int deg[200005];
int root[200005];
vector < pair < int , pair < int , int > > > road;
priority_queue < pair < int , int > , vector < pair < int , int > > , greater < pair < int , int > > > dij;
priority_queue < pair < int , int > , vector < pair < int , int > > , less < pair < int , int > > > dij2;
int small[200005];
//int deg[200005];
bool have[200005]={0};
bool cmp(pair < int , pair < int , int > > a,pair < int , pair < int , int > > b)
{
return a>b;
}
int Find(int here)
{
if(root[here]==here) return here;
root[here]=Find(root[here]);
return root[here];
}
void F(int here,int fa,int deg)
{
int j;
::deg[here]=deg;
for(auto i:Next2[here])
{
if(i.first==fa) continue;
Father[0][i.first]=make_pair(here,i.second);
for(j=1;j<25;j++)
{
Father[j][i.first].first=Father[j-1][Father[j-1][i.first].first].first;
Father[j][i.first].second=min(Father[j-1][Father[j-1][i.first].first].second,Father[j-1][i.first].second);
}
F(i.first,here,deg+1);
}
}
int LCA(int a,int b)
{
int j;
if(a==b) return 1e9;
if(deg[a]==deg[b])
{
if(Father[0][a].first==Father[0][b].first) return min(Father[0][a].second,Father[0][b].second);
else
{
for(j=20;j>=0;j--) if(Father[j][a].first!=Father[j][b].first) return min(min(Father[j][a].second,Father[j][b].second),LCA(Father[j][a].first,Father[j][b].first));
}
}
else
{
if(deg[a]<deg[b]) swap(a,b);
for(j=20;j>=0;j--) if(deg[a]-(1<<j)>=deg[b]) return min(Father[j][a].second,LCA(Father[j][a].first,b));
}
}
int main()
{
int N,M,K,Q,i,j,k,a,b,c,d,t;
scanf("%d %d",&N,&M);
for(i=0;i<M;i++)
{
scanf("%d %d %d",&a,&b,&c);
Next[a].push_back(make_pair(b,c));
Next[b].push_back(make_pair(a,c));
}
scanf("%d",&K);
while(K--)
{
scanf("%d",&t);
dij.push(make_pair(0,t));
}
while(!dij.empty())
{
a=dij.top().second;
b=dij.top().first;
dij.pop();
if(have[a]) continue;
//printf("%d %d\n",a,b);
have[a]=1;
small[a]=b;
for(auto i:Next[a]) dij.push(make_pair(b+i.second,i.first));
}
for(i=1;i<=N;i++) for(auto j:Next[i]) road.push_back(make_pair(min(small[i],small[j.first]),make_pair(i,j.first)));
sort(road.begin(),road.end(),cmp);
for(i=0;i<=N;i++)
{
root[i]=i;
for(j=0;j<25;j++) Father[j][i]=make_pair(0,1e9);
}
for(auto i:road)
{
if(Find(i.second.first)!=Find(i.second.second))
{
Next2[i.second.first].push_back(make_pair(i.second.second,i.first));
Next2[i.second.second].push_back(make_pair(i.second.first,i.first));
root[Find(i.second.first)]=Find(i.second.second);
}
}
F(1,-1,0);
scanf("%d",&Q);
while(Q--)
{
scanf("%d %d",&c,&d);
printf("%d\n",LCA(c,d));
}
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
*/
Compilation message
plan.cpp: In function 'int main()':
plan.cpp:69:21: warning: unused variable 'k' [-Wunused-variable]
69 | int N,M,K,Q,i,j,k,a,b,c,d,t;
| ^
plan.cpp: In function 'int LCA(int, int)':
plan.cpp:66:1: warning: control reaches end of non-void function [-Wreturn-type]
66 | }
| ^
plan.cpp: In function 'int main()':
plan.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
70 | scanf("%d %d",&N,&M);
| ~~~~~^~~~~~~~~~~~~~~
plan.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
73 | scanf("%d %d %d",&a,&b,&c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
plan.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
77 | scanf("%d",&K);
| ~~~~~^~~~~~~~~
plan.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
80 | scanf("%d",&t);
| ~~~~~^~~~~~~~~
plan.cpp:112:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
112 | scanf("%d",&Q);
| ~~~~~^~~~~~~~~
plan.cpp:115:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
115 | scanf("%d %d",&c,&d);
| ~~~~~^~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
9964 KB |
Output is correct |
2 |
Correct |
9 ms |
10220 KB |
Output is correct |
3 |
Correct |
9 ms |
10220 KB |
Output is correct |
4 |
Correct |
7 ms |
9964 KB |
Output is correct |
5 |
Correct |
9 ms |
10220 KB |
Output is correct |
6 |
Correct |
9 ms |
10220 KB |
Output is correct |
7 |
Correct |
7 ms |
9964 KB |
Output is correct |
8 |
Correct |
7 ms |
9964 KB |
Output is correct |
9 |
Correct |
9 ms |
10220 KB |
Output is correct |
10 |
Correct |
9 ms |
10220 KB |
Output is correct |
11 |
Correct |
9 ms |
10220 KB |
Output is correct |
12 |
Correct |
9 ms |
10220 KB |
Output is correct |
13 |
Correct |
9 ms |
10220 KB |
Output is correct |
14 |
Correct |
9 ms |
10220 KB |
Output is correct |
15 |
Correct |
9 ms |
10220 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
9964 KB |
Output is correct |
2 |
Correct |
9 ms |
10220 KB |
Output is correct |
3 |
Correct |
9 ms |
10220 KB |
Output is correct |
4 |
Correct |
7 ms |
9964 KB |
Output is correct |
5 |
Correct |
9 ms |
10220 KB |
Output is correct |
6 |
Correct |
9 ms |
10220 KB |
Output is correct |
7 |
Correct |
7 ms |
9964 KB |
Output is correct |
8 |
Correct |
7 ms |
9964 KB |
Output is correct |
9 |
Correct |
9 ms |
10220 KB |
Output is correct |
10 |
Correct |
9 ms |
10220 KB |
Output is correct |
11 |
Correct |
9 ms |
10220 KB |
Output is correct |
12 |
Correct |
9 ms |
10220 KB |
Output is correct |
13 |
Correct |
9 ms |
10220 KB |
Output is correct |
14 |
Correct |
9 ms |
10220 KB |
Output is correct |
15 |
Correct |
9 ms |
10220 KB |
Output is correct |
16 |
Correct |
333 ms |
35416 KB |
Output is correct |
17 |
Correct |
1212 ms |
68536 KB |
Output is correct |
18 |
Correct |
78 ms |
15452 KB |
Output is correct |
19 |
Correct |
237 ms |
43356 KB |
Output is correct |
20 |
Correct |
1196 ms |
68568 KB |
Output is correct |
21 |
Correct |
589 ms |
47188 KB |
Output is correct |
22 |
Correct |
297 ms |
46432 KB |
Output is correct |
23 |
Correct |
1244 ms |
68364 KB |
Output is correct |
24 |
Correct |
1189 ms |
68408 KB |
Output is correct |
25 |
Correct |
1213 ms |
68432 KB |
Output is correct |
26 |
Correct |
219 ms |
43740 KB |
Output is correct |
27 |
Correct |
226 ms |
43612 KB |
Output is correct |
28 |
Correct |
225 ms |
42332 KB |
Output is correct |
29 |
Correct |
233 ms |
43612 KB |
Output is correct |
30 |
Correct |
244 ms |
43228 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
9964 KB |
Output is correct |
2 |
Correct |
7 ms |
9964 KB |
Output is correct |
3 |
Correct |
8 ms |
9964 KB |
Output is correct |
4 |
Correct |
7 ms |
9964 KB |
Output is correct |
5 |
Correct |
7 ms |
9964 KB |
Output is correct |
6 |
Correct |
7 ms |
9964 KB |
Output is correct |
7 |
Correct |
7 ms |
9964 KB |
Output is correct |
8 |
Correct |
7 ms |
9964 KB |
Output is correct |
9 |
Correct |
7 ms |
9964 KB |
Output is correct |
10 |
Correct |
7 ms |
9888 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
464 ms |
46164 KB |
Output is correct |
2 |
Correct |
1026 ms |
68056 KB |
Output is correct |
3 |
Correct |
1050 ms |
68068 KB |
Output is correct |
4 |
Correct |
251 ms |
43228 KB |
Output is correct |
5 |
Correct |
1040 ms |
67952 KB |
Output is correct |
6 |
Correct |
1055 ms |
67896 KB |
Output is correct |
7 |
Correct |
1035 ms |
68152 KB |
Output is correct |
8 |
Correct |
1026 ms |
68024 KB |
Output is correct |
9 |
Correct |
1008 ms |
68024 KB |
Output is correct |
10 |
Correct |
1050 ms |
68024 KB |
Output is correct |
11 |
Correct |
1052 ms |
68152 KB |
Output is correct |
12 |
Correct |
1090 ms |
68076 KB |
Output is correct |
13 |
Correct |
1206 ms |
67916 KB |
Output is correct |
14 |
Correct |
1068 ms |
68000 KB |
Output is correct |
15 |
Correct |
1069 ms |
68172 KB |
Output is correct |
16 |
Correct |
1129 ms |
67896 KB |
Output is correct |
17 |
Correct |
1106 ms |
67920 KB |
Output is correct |
18 |
Correct |
1112 ms |
67876 KB |
Output is correct |
19 |
Correct |
292 ms |
45320 KB |
Output is correct |
20 |
Correct |
1104 ms |
67964 KB |
Output is correct |
21 |
Correct |
1040 ms |
69136 KB |
Output is correct |
22 |
Correct |
191 ms |
42996 KB |
Output is correct |
23 |
Correct |
247 ms |
40948 KB |
Output is correct |
24 |
Correct |
189 ms |
43388 KB |
Output is correct |
25 |
Correct |
193 ms |
42128 KB |
Output is correct |
26 |
Correct |
273 ms |
41436 KB |
Output is correct |
27 |
Correct |
266 ms |
45024 KB |
Output is correct |
28 |
Correct |
187 ms |
43484 KB |
Output is correct |
29 |
Correct |
258 ms |
44128 KB |
Output is correct |
30 |
Correct |
194 ms |
44764 KB |
Output is correct |
31 |
Correct |
255 ms |
44108 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
9964 KB |
Output is correct |
2 |
Correct |
9 ms |
10220 KB |
Output is correct |
3 |
Correct |
9 ms |
10220 KB |
Output is correct |
4 |
Correct |
7 ms |
9964 KB |
Output is correct |
5 |
Correct |
9 ms |
10220 KB |
Output is correct |
6 |
Correct |
9 ms |
10220 KB |
Output is correct |
7 |
Correct |
7 ms |
9964 KB |
Output is correct |
8 |
Correct |
7 ms |
9964 KB |
Output is correct |
9 |
Correct |
9 ms |
10220 KB |
Output is correct |
10 |
Correct |
9 ms |
10220 KB |
Output is correct |
11 |
Correct |
9 ms |
10220 KB |
Output is correct |
12 |
Correct |
9 ms |
10220 KB |
Output is correct |
13 |
Correct |
9 ms |
10220 KB |
Output is correct |
14 |
Correct |
9 ms |
10220 KB |
Output is correct |
15 |
Correct |
9 ms |
10220 KB |
Output is correct |
16 |
Correct |
333 ms |
35416 KB |
Output is correct |
17 |
Correct |
1212 ms |
68536 KB |
Output is correct |
18 |
Correct |
78 ms |
15452 KB |
Output is correct |
19 |
Correct |
237 ms |
43356 KB |
Output is correct |
20 |
Correct |
1196 ms |
68568 KB |
Output is correct |
21 |
Correct |
589 ms |
47188 KB |
Output is correct |
22 |
Correct |
297 ms |
46432 KB |
Output is correct |
23 |
Correct |
1244 ms |
68364 KB |
Output is correct |
24 |
Correct |
1189 ms |
68408 KB |
Output is correct |
25 |
Correct |
1213 ms |
68432 KB |
Output is correct |
26 |
Correct |
219 ms |
43740 KB |
Output is correct |
27 |
Correct |
226 ms |
43612 KB |
Output is correct |
28 |
Correct |
225 ms |
42332 KB |
Output is correct |
29 |
Correct |
233 ms |
43612 KB |
Output is correct |
30 |
Correct |
244 ms |
43228 KB |
Output is correct |
31 |
Correct |
7 ms |
9964 KB |
Output is correct |
32 |
Correct |
7 ms |
9964 KB |
Output is correct |
33 |
Correct |
8 ms |
9964 KB |
Output is correct |
34 |
Correct |
7 ms |
9964 KB |
Output is correct |
35 |
Correct |
7 ms |
9964 KB |
Output is correct |
36 |
Correct |
7 ms |
9964 KB |
Output is correct |
37 |
Correct |
7 ms |
9964 KB |
Output is correct |
38 |
Correct |
7 ms |
9964 KB |
Output is correct |
39 |
Correct |
7 ms |
9964 KB |
Output is correct |
40 |
Correct |
7 ms |
9888 KB |
Output is correct |
41 |
Correct |
464 ms |
46164 KB |
Output is correct |
42 |
Correct |
1026 ms |
68056 KB |
Output is correct |
43 |
Correct |
1050 ms |
68068 KB |
Output is correct |
44 |
Correct |
251 ms |
43228 KB |
Output is correct |
45 |
Correct |
1040 ms |
67952 KB |
Output is correct |
46 |
Correct |
1055 ms |
67896 KB |
Output is correct |
47 |
Correct |
1035 ms |
68152 KB |
Output is correct |
48 |
Correct |
1026 ms |
68024 KB |
Output is correct |
49 |
Correct |
1008 ms |
68024 KB |
Output is correct |
50 |
Correct |
1050 ms |
68024 KB |
Output is correct |
51 |
Correct |
1052 ms |
68152 KB |
Output is correct |
52 |
Correct |
1090 ms |
68076 KB |
Output is correct |
53 |
Correct |
1206 ms |
67916 KB |
Output is correct |
54 |
Correct |
1068 ms |
68000 KB |
Output is correct |
55 |
Correct |
1069 ms |
68172 KB |
Output is correct |
56 |
Correct |
1129 ms |
67896 KB |
Output is correct |
57 |
Correct |
1106 ms |
67920 KB |
Output is correct |
58 |
Correct |
1112 ms |
67876 KB |
Output is correct |
59 |
Correct |
292 ms |
45320 KB |
Output is correct |
60 |
Correct |
1104 ms |
67964 KB |
Output is correct |
61 |
Correct |
1040 ms |
69136 KB |
Output is correct |
62 |
Correct |
191 ms |
42996 KB |
Output is correct |
63 |
Correct |
247 ms |
40948 KB |
Output is correct |
64 |
Correct |
189 ms |
43388 KB |
Output is correct |
65 |
Correct |
193 ms |
42128 KB |
Output is correct |
66 |
Correct |
273 ms |
41436 KB |
Output is correct |
67 |
Correct |
266 ms |
45024 KB |
Output is correct |
68 |
Correct |
187 ms |
43484 KB |
Output is correct |
69 |
Correct |
258 ms |
44128 KB |
Output is correct |
70 |
Correct |
194 ms |
44764 KB |
Output is correct |
71 |
Correct |
255 ms |
44108 KB |
Output is correct |
72 |
Correct |
670 ms |
46736 KB |
Output is correct |
73 |
Correct |
1309 ms |
68308 KB |
Output is correct |
74 |
Correct |
1263 ms |
68328 KB |
Output is correct |
75 |
Correct |
1273 ms |
68320 KB |
Output is correct |
76 |
Correct |
1314 ms |
68268 KB |
Output is correct |
77 |
Correct |
1305 ms |
68296 KB |
Output is correct |
78 |
Correct |
1258 ms |
68316 KB |
Output is correct |
79 |
Correct |
1287 ms |
68280 KB |
Output is correct |
80 |
Correct |
1226 ms |
68380 KB |
Output is correct |
81 |
Correct |
1224 ms |
68296 KB |
Output is correct |
82 |
Correct |
1262 ms |
68392 KB |
Output is correct |
83 |
Correct |
1257 ms |
68280 KB |
Output is correct |
84 |
Correct |
1273 ms |
68284 KB |
Output is correct |
85 |
Correct |
1401 ms |
68396 KB |
Output is correct |
86 |
Correct |
1283 ms |
68332 KB |
Output is correct |
87 |
Correct |
1258 ms |
68300 KB |
Output is correct |
88 |
Correct |
1271 ms |
68292 KB |
Output is correct |
89 |
Correct |
512 ms |
45232 KB |
Output is correct |
90 |
Correct |
1300 ms |
68308 KB |
Output is correct |
91 |
Correct |
1206 ms |
69304 KB |
Output is correct |
92 |
Correct |
243 ms |
42484 KB |
Output is correct |
93 |
Correct |
490 ms |
41832 KB |
Output is correct |
94 |
Correct |
227 ms |
44508 KB |
Output is correct |
95 |
Correct |
239 ms |
43260 KB |
Output is correct |
96 |
Correct |
477 ms |
41872 KB |
Output is correct |
97 |
Correct |
543 ms |
43872 KB |
Output is correct |
98 |
Correct |
243 ms |
44252 KB |
Output is correct |
99 |
Correct |
474 ms |
45456 KB |
Output is correct |
100 |
Correct |
238 ms |
43740 KB |
Output is correct |