#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
int n , m , k , d[100005] , pai[100005] , peso[100005] , fn[100005] , sparse[100005][22] , custo[100005] , anc[100005][22] , h[100005];
vector<pii> adj[100005];
struct edges{
int x , y, z;
};
bool cmp(edges a , edges b){
return a.z > b.z;
}
void pre(int i , int j){
if(i == j) h[i] = 0;
for(int y = 0 ; y < adj[i].size();y++){
pii v = adj[i][y];
if(v.S == j) continue;
fn[v.S] = i;
custo[v.S] = v.F;
h[v.S] = h[i] + 1;
pre(v.S , i);
}
}
int fd(int x){ return pai[x] == x ? x : pai[x] = fd(pai[x]);}
void join(int u , int v){
u = fd(u) , v = fd(v);
if(peso[u] > peso[v]) swap(u,v);
pai[u] = v, peso[v] += peso[u] + 1;
}
int query(int x , int y){
if(h[x] < h[y]) swap(x,y);
int ansj = 1000000000;
for(int i = 21 ; i >= 0 ; i--){
while(h[x] >= h[y] + (1<<i)){
ansj = min(ansj , sparse[x][i]);
x = anc[x][i];
}
}
if(x == y) return ansj;
for(int i = 21 ; i >= 0 ; i--){
if(anc[x][i] != anc[y][i] && anc[x][i] != -1){
ansj = min(ansj , sparse[x][i]);
ansj = min(ansj , sparse[y][i]);
x = anc[x][i] , y = anc[y][i];
}
}
ansj = min(ansj , sparse[x][0]);
ansj = min(ansj , sparse[y][0]);
return ansj;
}
int main(){
scanf("%d%d" , &n, &m);
vector<edges> v;
for(int i = 0 ; i <n;i++){
pai[i] = i , peso[i] = 0 , d[i] = (int) 1e9;
}
for(int i = 0 ; i < m ; i++){
int x,y,z;
scanf("%d%d%d" , &x , &y , &z);
x--, y--;
v.pb({x,y,z});
adj[x].pb(pii(z,y));
adj[y].pb(pii(z,x));
}
scanf("%d" , &k);
priority_queue<pii , vector<pii> , greater<pii> > pq;
for(int i = 0 ; i < k ; i++) {
int x;
scanf("%d" , &x);
x--;
d[x] = 0;
pq.push(pii(0,x));
}
while(!pq.empty()){
pii u = pq.top();
pq.pop();
if(d[u.S] != u.F) continue;
for(int j = 0 ; j < adj[u.S].size();j++){
pii v = adj[u.S][j];
if(d[v.S] > v.F + u.F){
d[v.S] = v.F + u.F;
pq.push(pii(d[v.S] , v.S));
}
}
}
for(int i = 0 ; i < m ; i++){
v[i].z = min(d[v[i].x] , d[v[i].y]);
adj[v[i].x].clear();
adj[v[i].y].clear();
}
sort(v.begin() , v.end() , cmp);
for(int i = 0 ; i <m;i++){
if(fd(v[i].x) != fd(v[i].y)){
join(v[i].x , v[i].y);
adj[v[i].x].pb(pii(v[i].z , v[i].y));
adj[v[i].y].pb(pii(v[i].z , v[i].x));
}
}
for(int i = 0 ; i < 100005 ; i++)
for(int j = 0 ; j < 22 ; j++) anc[i][j] = -1 , sparse[i][j] = 1000000009;
memset(fn , -1 , sizeof fn);
pre(0 , 0);
for(int i = 0 ; i < 100005 ; i++){
if(fn[i] != -1) anc[i][0] = fn[i] , sparse[i][0] = custo[i];
}
for(int j = 1; j < 22 ; j++){
for(int i = 0 ; i < 100005;i++){
if(anc[i][j-1] != -1) anc[i][j] = anc[anc[i][j-1]][j-1] , sparse[i][j] = min(sparse[i][j] , min(sparse[i][j-1] , sparse[anc[i][j-1]][j-1]));
}
}
int q;
scanf("%d" , &q);
while(q--){
int x,y;
scanf("%d%d" , &x , &y);
x-- ,y--;
printf("%d\n" , query(x,y));
}
}
Compilation message
plan.cpp: In function 'void pre(int, int)':
plan.cpp:21:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int y = 0 ; y < adj[i].size();y++){
~~^~~~~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:89:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0 ; j < adj[u.S].size();j++){
~~^~~~~~~~~~~~~~~~~
plan.cpp:63:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d" , &n, &m);
~~~~~^~~~~~~~~~~~~~~~~~
plan.cpp:70:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d" , &x , &y , &z);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:76:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d" , &k);
~~~~~^~~~~~~~~~~
plan.cpp:80:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d" , &x);
~~~~~^~~~~~~~~~~
plan.cpp:124:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d" , &q);
~~~~~^~~~~~~~~~~
plan.cpp:127:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d" , &x , &y);
~~~~~^~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
20344 KB |
Output is correct |
2 |
Correct |
28 ms |
20324 KB |
Output is correct |
3 |
Correct |
31 ms |
20344 KB |
Output is correct |
4 |
Correct |
27 ms |
20344 KB |
Output is correct |
5 |
Correct |
28 ms |
20344 KB |
Output is correct |
6 |
Correct |
28 ms |
20344 KB |
Output is correct |
7 |
Correct |
27 ms |
20344 KB |
Output is correct |
8 |
Correct |
27 ms |
20344 KB |
Output is correct |
9 |
Correct |
28 ms |
20344 KB |
Output is correct |
10 |
Correct |
28 ms |
20344 KB |
Output is correct |
11 |
Correct |
29 ms |
20412 KB |
Output is correct |
12 |
Correct |
29 ms |
20412 KB |
Output is correct |
13 |
Correct |
29 ms |
20456 KB |
Output is correct |
14 |
Correct |
29 ms |
20364 KB |
Output is correct |
15 |
Correct |
29 ms |
20424 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
20344 KB |
Output is correct |
2 |
Correct |
28 ms |
20324 KB |
Output is correct |
3 |
Correct |
31 ms |
20344 KB |
Output is correct |
4 |
Correct |
27 ms |
20344 KB |
Output is correct |
5 |
Correct |
28 ms |
20344 KB |
Output is correct |
6 |
Correct |
28 ms |
20344 KB |
Output is correct |
7 |
Correct |
27 ms |
20344 KB |
Output is correct |
8 |
Correct |
27 ms |
20344 KB |
Output is correct |
9 |
Correct |
28 ms |
20344 KB |
Output is correct |
10 |
Correct |
28 ms |
20344 KB |
Output is correct |
11 |
Correct |
29 ms |
20412 KB |
Output is correct |
12 |
Correct |
29 ms |
20412 KB |
Output is correct |
13 |
Correct |
29 ms |
20456 KB |
Output is correct |
14 |
Correct |
29 ms |
20364 KB |
Output is correct |
15 |
Correct |
29 ms |
20424 KB |
Output is correct |
16 |
Correct |
216 ms |
27816 KB |
Output is correct |
17 |
Correct |
685 ms |
45080 KB |
Output is correct |
18 |
Correct |
69 ms |
22704 KB |
Output is correct |
19 |
Correct |
190 ms |
29856 KB |
Output is correct |
20 |
Correct |
657 ms |
45032 KB |
Output is correct |
21 |
Correct |
343 ms |
33156 KB |
Output is correct |
22 |
Correct |
223 ms |
32536 KB |
Output is correct |
23 |
Correct |
661 ms |
45248 KB |
Output is correct |
24 |
Correct |
643 ms |
45540 KB |
Output is correct |
25 |
Correct |
663 ms |
45092 KB |
Output is correct |
26 |
Correct |
186 ms |
29728 KB |
Output is correct |
27 |
Correct |
194 ms |
29828 KB |
Output is correct |
28 |
Correct |
193 ms |
29776 KB |
Output is correct |
29 |
Correct |
194 ms |
29908 KB |
Output is correct |
30 |
Correct |
194 ms |
29948 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
20252 KB |
Output is correct |
2 |
Correct |
26 ms |
20316 KB |
Output is correct |
3 |
Correct |
27 ms |
20356 KB |
Output is correct |
4 |
Correct |
26 ms |
20292 KB |
Output is correct |
5 |
Correct |
27 ms |
20228 KB |
Output is correct |
6 |
Correct |
27 ms |
20344 KB |
Output is correct |
7 |
Correct |
26 ms |
20344 KB |
Output is correct |
8 |
Correct |
27 ms |
20344 KB |
Output is correct |
9 |
Correct |
27 ms |
20344 KB |
Output is correct |
10 |
Correct |
27 ms |
20348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
280 ms |
32268 KB |
Output is correct |
2 |
Correct |
589 ms |
44708 KB |
Output is correct |
3 |
Correct |
590 ms |
44968 KB |
Output is correct |
4 |
Correct |
173 ms |
29816 KB |
Output is correct |
5 |
Correct |
619 ms |
44704 KB |
Output is correct |
6 |
Correct |
584 ms |
44948 KB |
Output is correct |
7 |
Correct |
559 ms |
44824 KB |
Output is correct |
8 |
Correct |
581 ms |
44764 KB |
Output is correct |
9 |
Correct |
585 ms |
44128 KB |
Output is correct |
10 |
Correct |
574 ms |
44256 KB |
Output is correct |
11 |
Correct |
585 ms |
44104 KB |
Output is correct |
12 |
Correct |
585 ms |
44144 KB |
Output is correct |
13 |
Correct |
571 ms |
44128 KB |
Output is correct |
14 |
Correct |
571 ms |
44256 KB |
Output is correct |
15 |
Correct |
585 ms |
45304 KB |
Output is correct |
16 |
Correct |
579 ms |
44184 KB |
Output is correct |
17 |
Correct |
588 ms |
44204 KB |
Output is correct |
18 |
Correct |
577 ms |
44136 KB |
Output is correct |
19 |
Correct |
159 ms |
31080 KB |
Output is correct |
20 |
Correct |
603 ms |
44156 KB |
Output is correct |
21 |
Correct |
550 ms |
43900 KB |
Output is correct |
22 |
Correct |
138 ms |
29080 KB |
Output is correct |
23 |
Correct |
165 ms |
27540 KB |
Output is correct |
24 |
Correct |
166 ms |
29096 KB |
Output is correct |
25 |
Correct |
141 ms |
29116 KB |
Output is correct |
26 |
Correct |
167 ms |
27816 KB |
Output is correct |
27 |
Correct |
167 ms |
30764 KB |
Output is correct |
28 |
Correct |
137 ms |
29108 KB |
Output is correct |
29 |
Correct |
165 ms |
30040 KB |
Output is correct |
30 |
Correct |
136 ms |
29116 KB |
Output is correct |
31 |
Correct |
168 ms |
30124 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
20344 KB |
Output is correct |
2 |
Correct |
28 ms |
20324 KB |
Output is correct |
3 |
Correct |
31 ms |
20344 KB |
Output is correct |
4 |
Correct |
27 ms |
20344 KB |
Output is correct |
5 |
Correct |
28 ms |
20344 KB |
Output is correct |
6 |
Correct |
28 ms |
20344 KB |
Output is correct |
7 |
Correct |
27 ms |
20344 KB |
Output is correct |
8 |
Correct |
27 ms |
20344 KB |
Output is correct |
9 |
Correct |
28 ms |
20344 KB |
Output is correct |
10 |
Correct |
28 ms |
20344 KB |
Output is correct |
11 |
Correct |
29 ms |
20412 KB |
Output is correct |
12 |
Correct |
29 ms |
20412 KB |
Output is correct |
13 |
Correct |
29 ms |
20456 KB |
Output is correct |
14 |
Correct |
29 ms |
20364 KB |
Output is correct |
15 |
Correct |
29 ms |
20424 KB |
Output is correct |
16 |
Correct |
216 ms |
27816 KB |
Output is correct |
17 |
Correct |
685 ms |
45080 KB |
Output is correct |
18 |
Correct |
69 ms |
22704 KB |
Output is correct |
19 |
Correct |
190 ms |
29856 KB |
Output is correct |
20 |
Correct |
657 ms |
45032 KB |
Output is correct |
21 |
Correct |
343 ms |
33156 KB |
Output is correct |
22 |
Correct |
223 ms |
32536 KB |
Output is correct |
23 |
Correct |
661 ms |
45248 KB |
Output is correct |
24 |
Correct |
643 ms |
45540 KB |
Output is correct |
25 |
Correct |
663 ms |
45092 KB |
Output is correct |
26 |
Correct |
186 ms |
29728 KB |
Output is correct |
27 |
Correct |
194 ms |
29828 KB |
Output is correct |
28 |
Correct |
193 ms |
29776 KB |
Output is correct |
29 |
Correct |
194 ms |
29908 KB |
Output is correct |
30 |
Correct |
194 ms |
29948 KB |
Output is correct |
31 |
Correct |
27 ms |
20252 KB |
Output is correct |
32 |
Correct |
26 ms |
20316 KB |
Output is correct |
33 |
Correct |
27 ms |
20356 KB |
Output is correct |
34 |
Correct |
26 ms |
20292 KB |
Output is correct |
35 |
Correct |
27 ms |
20228 KB |
Output is correct |
36 |
Correct |
27 ms |
20344 KB |
Output is correct |
37 |
Correct |
26 ms |
20344 KB |
Output is correct |
38 |
Correct |
27 ms |
20344 KB |
Output is correct |
39 |
Correct |
27 ms |
20344 KB |
Output is correct |
40 |
Correct |
27 ms |
20348 KB |
Output is correct |
41 |
Correct |
280 ms |
32268 KB |
Output is correct |
42 |
Correct |
589 ms |
44708 KB |
Output is correct |
43 |
Correct |
590 ms |
44968 KB |
Output is correct |
44 |
Correct |
173 ms |
29816 KB |
Output is correct |
45 |
Correct |
619 ms |
44704 KB |
Output is correct |
46 |
Correct |
584 ms |
44948 KB |
Output is correct |
47 |
Correct |
559 ms |
44824 KB |
Output is correct |
48 |
Correct |
581 ms |
44764 KB |
Output is correct |
49 |
Correct |
585 ms |
44128 KB |
Output is correct |
50 |
Correct |
574 ms |
44256 KB |
Output is correct |
51 |
Correct |
585 ms |
44104 KB |
Output is correct |
52 |
Correct |
585 ms |
44144 KB |
Output is correct |
53 |
Correct |
571 ms |
44128 KB |
Output is correct |
54 |
Correct |
571 ms |
44256 KB |
Output is correct |
55 |
Correct |
585 ms |
45304 KB |
Output is correct |
56 |
Correct |
579 ms |
44184 KB |
Output is correct |
57 |
Correct |
588 ms |
44204 KB |
Output is correct |
58 |
Correct |
577 ms |
44136 KB |
Output is correct |
59 |
Correct |
159 ms |
31080 KB |
Output is correct |
60 |
Correct |
603 ms |
44156 KB |
Output is correct |
61 |
Correct |
550 ms |
43900 KB |
Output is correct |
62 |
Correct |
138 ms |
29080 KB |
Output is correct |
63 |
Correct |
165 ms |
27540 KB |
Output is correct |
64 |
Correct |
166 ms |
29096 KB |
Output is correct |
65 |
Correct |
141 ms |
29116 KB |
Output is correct |
66 |
Correct |
167 ms |
27816 KB |
Output is correct |
67 |
Correct |
167 ms |
30764 KB |
Output is correct |
68 |
Correct |
137 ms |
29108 KB |
Output is correct |
69 |
Correct |
165 ms |
30040 KB |
Output is correct |
70 |
Correct |
136 ms |
29116 KB |
Output is correct |
71 |
Correct |
168 ms |
30124 KB |
Output is correct |
72 |
Correct |
367 ms |
32576 KB |
Output is correct |
73 |
Correct |
662 ms |
44600 KB |
Output is correct |
74 |
Correct |
705 ms |
44768 KB |
Output is correct |
75 |
Correct |
662 ms |
44656 KB |
Output is correct |
76 |
Correct |
699 ms |
44572 KB |
Output is correct |
77 |
Correct |
658 ms |
44540 KB |
Output is correct |
78 |
Correct |
652 ms |
44656 KB |
Output is correct |
79 |
Correct |
664 ms |
44668 KB |
Output is correct |
80 |
Correct |
678 ms |
44916 KB |
Output is correct |
81 |
Correct |
648 ms |
45316 KB |
Output is correct |
82 |
Correct |
647 ms |
44912 KB |
Output is correct |
83 |
Correct |
654 ms |
44996 KB |
Output is correct |
84 |
Correct |
657 ms |
45240 KB |
Output is correct |
85 |
Correct |
665 ms |
46376 KB |
Output is correct |
86 |
Correct |
706 ms |
45232 KB |
Output is correct |
87 |
Correct |
654 ms |
45080 KB |
Output is correct |
88 |
Correct |
680 ms |
45408 KB |
Output is correct |
89 |
Correct |
312 ms |
31444 KB |
Output is correct |
90 |
Correct |
703 ms |
45180 KB |
Output is correct |
91 |
Correct |
636 ms |
45216 KB |
Output is correct |
92 |
Correct |
204 ms |
30248 KB |
Output is correct |
93 |
Correct |
267 ms |
29008 KB |
Output is correct |
94 |
Correct |
200 ms |
30116 KB |
Output is correct |
95 |
Correct |
199 ms |
30232 KB |
Output is correct |
96 |
Correct |
253 ms |
29072 KB |
Output is correct |
97 |
Correct |
292 ms |
31148 KB |
Output is correct |
98 |
Correct |
200 ms |
30112 KB |
Output is correct |
99 |
Correct |
296 ms |
31876 KB |
Output is correct |
100 |
Correct |
208 ms |
30272 KB |
Output is correct |