#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define mk make_pair
#define all(s) s.begin(),s.end()
//#define int long long
using namespace std;
const int N = (1e5 + 12);
const int mod = (1e9 + 7);
const int INF = (0x3f3f3f3f);
vector<pair<int,int > > g[N];
vector<pair<int,pair<int,int > > > vec;
vector<pair<int,int > > road;
int dist[N], par[N], sz[N], up[20][N], mn[20][N], tin[N], tout[N], timer;
int find(int v){
if(v == par[v]){
return v;
}
return par[v] = find(par[v]);
}
void dsu(int a,int b){
a = find(a);
b = find(b);
if(sz[a] < sz[b]){
swap(a, b);
}
sz[a] += sz[b];
par[b] = a;
}
void dfs(int v,int pr,int w){
up[0][v] = pr;
mn[0][v] = w;
tin[v] = ++timer;
for(int i = 1;i <= 19; i++){
up[i][v] = up[i - 1][up[i - 1][v]];
mn[i][v] = min(mn[i - 1][v], mn[i - 1][up[i - 1][v]]);
}
for(auto to : g[v]){
if(to.fr != pr){
dfs(to.fr, v, to.sc);
}
}
tout[v] = ++timer;
}
bool upper(int a,int b){
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int get(int a,int b){
int res = INF;
if(upper(a, b)){
for(int i = 19;i >= 0; i--){
if(!upper(up[i][b], a)){
res = min(res, mn[i][b]);
b = up[i][b];
}
}
res = min(res, mn[0][b]);
}
else
if(upper(b, a)){
for(int i = 19;i >= 0; i--){
if(!upper(up[i][a], b)){
res = min(res, mn[i][a]);
a = up[i][a];
}
}
res = min(res, mn[0][a]);
}
else{
for(int i = 19;i >= 0; i--){
if(!upper(up[i][b], a)){
res = min(res, mn[i][b]);
b = up[i][b];
}
}
res = min(res, mn[0][b]);
for(int i = 19;i >= 0; i--){
if(!upper(up[i][a], b)){
res = min(res, mn[i][a]);
a = up[i][a];
}
}
res = min(res, mn[0][a]);
}
return res;
}
main()
{
int n, m, u, v, w;
scanf("%d%d", &n, &m);
for(int i = 1;i <= n; i++){
par[i] = i;
sz[i] = 1;
}
for(int i = 1;i <= m; i++){
scanf("%d%d%d", &u, &v, &w);
g[u].pb({v,w});
g[v].pb({u,w});
road.pb({u, v});
}
int k;
priority_queue<pair<int,int > > q;
scanf("%d", &k);
memset(dist, 0x3f3f3f3f,sizeof(dist));
for(int i = 0;i < k; i++){
scanf("%d", &v);
dist[v] = 0;
q.push({0,v});
}
while(!q.empty()){
v = q.top().sc;
q.pop();
for(auto to : g[v]){
if(dist[to.fr] > dist[v] + to.sc){
dist[to.fr] = dist[v] + to.sc;
q.push({-dist[to.fr], to.fr});
}
}
}
for(int i = 1;i <= n; i++){
g[i].clear();
}
for(int i = 0;i < m; i++){
vec.pb({min(dist[road[i].fr],dist[road[i].sc]),{road[i].fr,road[i].sc}});
}
sort(all(vec));
reverse(all(vec));
for(int i = 0;i < m; i++){
v = vec[i].sc.fr, u = vec[i].sc.sc, w = min(dist[u], dist[v]);
if(find(v) != find(u)){
g[v].pb({u, w});
g[u].pb({v, w});
dsu(u,v);
}
}
dfs(1, 1, INF);
int t;
scanf("%d", &t);
while(t--){
scanf("%d%d", &u, &v);
printf("%d\n", get(u, v));
}
}
Compilation message
plan.cpp:99:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main()
^
plan.cpp: In function 'int main()':
plan.cpp:102: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:108:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &u, &v, &w);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:115:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &k);
~~~~~^~~~~~~~~~
plan.cpp:118:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &v);
~~~~~^~~~~~~~~~
plan.cpp:150:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &t);
~~~~~^~~~~~~~~~
plan.cpp:152:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &u, &v);
~~~~~^~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
3192 KB |
Output is correct |
2 |
Correct |
6 ms |
3548 KB |
Output is correct |
3 |
Correct |
5 ms |
3448 KB |
Output is correct |
4 |
Correct |
4 ms |
3236 KB |
Output is correct |
5 |
Correct |
5 ms |
3448 KB |
Output is correct |
6 |
Correct |
6 ms |
3552 KB |
Output is correct |
7 |
Correct |
4 ms |
3320 KB |
Output is correct |
8 |
Correct |
4 ms |
3320 KB |
Output is correct |
9 |
Correct |
6 ms |
3576 KB |
Output is correct |
10 |
Correct |
6 ms |
3576 KB |
Output is correct |
11 |
Correct |
6 ms |
3576 KB |
Output is correct |
12 |
Correct |
6 ms |
3448 KB |
Output is correct |
13 |
Correct |
6 ms |
3452 KB |
Output is correct |
14 |
Correct |
6 ms |
3452 KB |
Output is correct |
15 |
Correct |
6 ms |
3548 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
3192 KB |
Output is correct |
2 |
Correct |
6 ms |
3548 KB |
Output is correct |
3 |
Correct |
5 ms |
3448 KB |
Output is correct |
4 |
Correct |
4 ms |
3236 KB |
Output is correct |
5 |
Correct |
5 ms |
3448 KB |
Output is correct |
6 |
Correct |
6 ms |
3552 KB |
Output is correct |
7 |
Correct |
4 ms |
3320 KB |
Output is correct |
8 |
Correct |
4 ms |
3320 KB |
Output is correct |
9 |
Correct |
6 ms |
3576 KB |
Output is correct |
10 |
Correct |
6 ms |
3576 KB |
Output is correct |
11 |
Correct |
6 ms |
3576 KB |
Output is correct |
12 |
Correct |
6 ms |
3448 KB |
Output is correct |
13 |
Correct |
6 ms |
3452 KB |
Output is correct |
14 |
Correct |
6 ms |
3452 KB |
Output is correct |
15 |
Correct |
6 ms |
3548 KB |
Output is correct |
16 |
Correct |
295 ms |
23724 KB |
Output is correct |
17 |
Correct |
862 ms |
49328 KB |
Output is correct |
18 |
Correct |
53 ms |
8172 KB |
Output is correct |
19 |
Correct |
207 ms |
28724 KB |
Output is correct |
20 |
Correct |
882 ms |
50164 KB |
Output is correct |
21 |
Correct |
504 ms |
34192 KB |
Output is correct |
22 |
Correct |
303 ms |
32408 KB |
Output is correct |
23 |
Correct |
841 ms |
50560 KB |
Output is correct |
24 |
Correct |
809 ms |
49828 KB |
Output is correct |
25 |
Correct |
898 ms |
49524 KB |
Output is correct |
26 |
Correct |
210 ms |
28456 KB |
Output is correct |
27 |
Correct |
216 ms |
28576 KB |
Output is correct |
28 |
Correct |
211 ms |
28600 KB |
Output is correct |
29 |
Correct |
212 ms |
28752 KB |
Output is correct |
30 |
Correct |
205 ms |
28116 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
3192 KB |
Output is correct |
2 |
Correct |
4 ms |
3192 KB |
Output is correct |
3 |
Correct |
5 ms |
3240 KB |
Output is correct |
4 |
Correct |
4 ms |
3192 KB |
Output is correct |
5 |
Correct |
4 ms |
3196 KB |
Output is correct |
6 |
Correct |
4 ms |
3236 KB |
Output is correct |
7 |
Correct |
4 ms |
3192 KB |
Output is correct |
8 |
Correct |
4 ms |
3192 KB |
Output is correct |
9 |
Correct |
4 ms |
3320 KB |
Output is correct |
10 |
Correct |
4 ms |
3320 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
639 ms |
33388 KB |
Output is correct |
2 |
Correct |
766 ms |
54996 KB |
Output is correct |
3 |
Correct |
768 ms |
54312 KB |
Output is correct |
4 |
Correct |
239 ms |
30644 KB |
Output is correct |
5 |
Correct |
743 ms |
53436 KB |
Output is correct |
6 |
Correct |
745 ms |
54692 KB |
Output is correct |
7 |
Correct |
745 ms |
55232 KB |
Output is correct |
8 |
Correct |
761 ms |
55652 KB |
Output is correct |
9 |
Correct |
751 ms |
54356 KB |
Output is correct |
10 |
Correct |
779 ms |
56248 KB |
Output is correct |
11 |
Correct |
786 ms |
56468 KB |
Output is correct |
12 |
Correct |
776 ms |
56552 KB |
Output is correct |
13 |
Correct |
752 ms |
56436 KB |
Output is correct |
14 |
Correct |
779 ms |
55796 KB |
Output is correct |
15 |
Correct |
731 ms |
56440 KB |
Output is correct |
16 |
Correct |
714 ms |
55616 KB |
Output is correct |
17 |
Correct |
756 ms |
56008 KB |
Output is correct |
18 |
Correct |
773 ms |
55616 KB |
Output is correct |
19 |
Correct |
284 ms |
32212 KB |
Output is correct |
20 |
Correct |
790 ms |
55072 KB |
Output is correct |
21 |
Correct |
762 ms |
55008 KB |
Output is correct |
22 |
Correct |
152 ms |
29344 KB |
Output is correct |
23 |
Correct |
280 ms |
28932 KB |
Output is correct |
24 |
Correct |
152 ms |
29356 KB |
Output is correct |
25 |
Correct |
152 ms |
29304 KB |
Output is correct |
26 |
Correct |
284 ms |
29328 KB |
Output is correct |
27 |
Correct |
232 ms |
32100 KB |
Output is correct |
28 |
Correct |
137 ms |
29400 KB |
Output is correct |
29 |
Correct |
237 ms |
31336 KB |
Output is correct |
30 |
Correct |
155 ms |
29400 KB |
Output is correct |
31 |
Correct |
263 ms |
31444 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
3192 KB |
Output is correct |
2 |
Correct |
6 ms |
3548 KB |
Output is correct |
3 |
Correct |
5 ms |
3448 KB |
Output is correct |
4 |
Correct |
4 ms |
3236 KB |
Output is correct |
5 |
Correct |
5 ms |
3448 KB |
Output is correct |
6 |
Correct |
6 ms |
3552 KB |
Output is correct |
7 |
Correct |
4 ms |
3320 KB |
Output is correct |
8 |
Correct |
4 ms |
3320 KB |
Output is correct |
9 |
Correct |
6 ms |
3576 KB |
Output is correct |
10 |
Correct |
6 ms |
3576 KB |
Output is correct |
11 |
Correct |
6 ms |
3576 KB |
Output is correct |
12 |
Correct |
6 ms |
3448 KB |
Output is correct |
13 |
Correct |
6 ms |
3452 KB |
Output is correct |
14 |
Correct |
6 ms |
3452 KB |
Output is correct |
15 |
Correct |
6 ms |
3548 KB |
Output is correct |
16 |
Correct |
295 ms |
23724 KB |
Output is correct |
17 |
Correct |
862 ms |
49328 KB |
Output is correct |
18 |
Correct |
53 ms |
8172 KB |
Output is correct |
19 |
Correct |
207 ms |
28724 KB |
Output is correct |
20 |
Correct |
882 ms |
50164 KB |
Output is correct |
21 |
Correct |
504 ms |
34192 KB |
Output is correct |
22 |
Correct |
303 ms |
32408 KB |
Output is correct |
23 |
Correct |
841 ms |
50560 KB |
Output is correct |
24 |
Correct |
809 ms |
49828 KB |
Output is correct |
25 |
Correct |
898 ms |
49524 KB |
Output is correct |
26 |
Correct |
210 ms |
28456 KB |
Output is correct |
27 |
Correct |
216 ms |
28576 KB |
Output is correct |
28 |
Correct |
211 ms |
28600 KB |
Output is correct |
29 |
Correct |
212 ms |
28752 KB |
Output is correct |
30 |
Correct |
205 ms |
28116 KB |
Output is correct |
31 |
Correct |
4 ms |
3192 KB |
Output is correct |
32 |
Correct |
4 ms |
3192 KB |
Output is correct |
33 |
Correct |
5 ms |
3240 KB |
Output is correct |
34 |
Correct |
4 ms |
3192 KB |
Output is correct |
35 |
Correct |
4 ms |
3196 KB |
Output is correct |
36 |
Correct |
4 ms |
3236 KB |
Output is correct |
37 |
Correct |
4 ms |
3192 KB |
Output is correct |
38 |
Correct |
4 ms |
3192 KB |
Output is correct |
39 |
Correct |
4 ms |
3320 KB |
Output is correct |
40 |
Correct |
4 ms |
3320 KB |
Output is correct |
41 |
Correct |
639 ms |
33388 KB |
Output is correct |
42 |
Correct |
766 ms |
54996 KB |
Output is correct |
43 |
Correct |
768 ms |
54312 KB |
Output is correct |
44 |
Correct |
239 ms |
30644 KB |
Output is correct |
45 |
Correct |
743 ms |
53436 KB |
Output is correct |
46 |
Correct |
745 ms |
54692 KB |
Output is correct |
47 |
Correct |
745 ms |
55232 KB |
Output is correct |
48 |
Correct |
761 ms |
55652 KB |
Output is correct |
49 |
Correct |
751 ms |
54356 KB |
Output is correct |
50 |
Correct |
779 ms |
56248 KB |
Output is correct |
51 |
Correct |
786 ms |
56468 KB |
Output is correct |
52 |
Correct |
776 ms |
56552 KB |
Output is correct |
53 |
Correct |
752 ms |
56436 KB |
Output is correct |
54 |
Correct |
779 ms |
55796 KB |
Output is correct |
55 |
Correct |
731 ms |
56440 KB |
Output is correct |
56 |
Correct |
714 ms |
55616 KB |
Output is correct |
57 |
Correct |
756 ms |
56008 KB |
Output is correct |
58 |
Correct |
773 ms |
55616 KB |
Output is correct |
59 |
Correct |
284 ms |
32212 KB |
Output is correct |
60 |
Correct |
790 ms |
55072 KB |
Output is correct |
61 |
Correct |
762 ms |
55008 KB |
Output is correct |
62 |
Correct |
152 ms |
29344 KB |
Output is correct |
63 |
Correct |
280 ms |
28932 KB |
Output is correct |
64 |
Correct |
152 ms |
29356 KB |
Output is correct |
65 |
Correct |
152 ms |
29304 KB |
Output is correct |
66 |
Correct |
284 ms |
29328 KB |
Output is correct |
67 |
Correct |
232 ms |
32100 KB |
Output is correct |
68 |
Correct |
137 ms |
29400 KB |
Output is correct |
69 |
Correct |
237 ms |
31336 KB |
Output is correct |
70 |
Correct |
155 ms |
29400 KB |
Output is correct |
71 |
Correct |
263 ms |
31444 KB |
Output is correct |
72 |
Correct |
530 ms |
37112 KB |
Output is correct |
73 |
Correct |
815 ms |
54748 KB |
Output is correct |
74 |
Correct |
858 ms |
55632 KB |
Output is correct |
75 |
Correct |
812 ms |
55312 KB |
Output is correct |
76 |
Correct |
901 ms |
55048 KB |
Output is correct |
77 |
Correct |
887 ms |
55184 KB |
Output is correct |
78 |
Correct |
862 ms |
54232 KB |
Output is correct |
79 |
Correct |
855 ms |
56516 KB |
Output is correct |
80 |
Correct |
855 ms |
55652 KB |
Output is correct |
81 |
Correct |
852 ms |
56116 KB |
Output is correct |
82 |
Correct |
842 ms |
55316 KB |
Output is correct |
83 |
Correct |
850 ms |
54456 KB |
Output is correct |
84 |
Correct |
927 ms |
52816 KB |
Output is correct |
85 |
Correct |
882 ms |
53764 KB |
Output is correct |
86 |
Correct |
875 ms |
54876 KB |
Output is correct |
87 |
Correct |
868 ms |
54004 KB |
Output is correct |
88 |
Correct |
876 ms |
53140 KB |
Output is correct |
89 |
Correct |
468 ms |
32524 KB |
Output is correct |
90 |
Correct |
919 ms |
54336 KB |
Output is correct |
91 |
Correct |
829 ms |
52280 KB |
Output is correct |
92 |
Correct |
232 ms |
30068 KB |
Output is correct |
93 |
Correct |
399 ms |
30100 KB |
Output is correct |
94 |
Correct |
242 ms |
30852 KB |
Output is correct |
95 |
Correct |
223 ms |
30904 KB |
Output is correct |
96 |
Correct |
379 ms |
29704 KB |
Output is correct |
97 |
Correct |
410 ms |
31632 KB |
Output is correct |
98 |
Correct |
249 ms |
30936 KB |
Output is correct |
99 |
Correct |
369 ms |
32860 KB |
Output is correct |
100 |
Correct |
226 ms |
30976 KB |
Output is correct |