#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100100 , L = 17 ;
int n , m , k , Q;
int p[N][L] , dep[N];
ll mn[N][L];
ll dis[N];
int par[N];
vector<pair<int,int>>adj[N];
vector<int>ADJ[N];
vector< pair< ll , pair<int,int> > >edges;
priority_queue<pair<ll,int>>pq;
int get(int x){
if( x == par[x] )return x;
return par[x]=get(par[x]);
}
void mrg(int x,int y){
x=get(x); y=get(y);
if( x == y )return;
if( rand()&1 )swap(x,y);
par[x]=y;
}
void dij(){
while( !pq.empty() ){
ll d = -pq.top().first;
int u = pq.top().second;
pq.pop();
if( d != dis[u] )continue;
for(auto e:adj[u]){
int v = e.first;
int w = e.second;
if( dis[v] > dis[u] + 1ll*w ){
dis[v] = dis[u] + 1ll*w;
pq.push( {-dis[v],v} );
}
}
}
}
void dfs(int u,int dad){
dep[u]=1+dep[dad];
p[u][0]=dad;
mn[u][0]=dis[u];
for(int j=1;j<L;j++){
p[u][j]=p[ p[u][j-1] ][j-1];
mn[u][j]=min(mn[u][j-1],mn[p[u][j-1]][j-1]);
}
for(auto v:ADJ[u])
if( v != dad )
dfs(v,u);
}
int LCA(int u,int v){
if( u == v )return u;
if( dep[u] < dep[v] )swap(u,v);
int k = dep[u]-dep[v];
for(int i=0;i<L;i++)
if( k & (1<<i) )
u=p[u][i];
if( u == v )return u;
for(int i=L-1;i>=0;i--)
if( p[u][i] != p[v][i] )
u=p[u][i],v=p[v][i];
return p[u][0];
}
ll f(int u,int k){
ll ret=mn[u][0];
for(int i=0;i<L;i++)
if( k&(1<<i) ){
ret=min(ret,mn[u][i]);
u=p[u][i];
}
return ret;
}
void solve(){
cin>>n>>m;
edges.clear();
for(int i=1;i<=n;i++){
dis[i]=1ll<<50;
adj[i].clear();
ADJ[i].clear();
par[i]=i;
for(int j=0;j<L;j++)
mn[i][j]=1ll<<50,p[i][j]=0;
}
while( !pq.empty() )pq.pop();
while( m-- ){
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
adj[u].push_back( {v,w} );
adj[v].push_back( {u,w} );
}
cin>>k;
for(int i=0;i<k;i++){
int x;
scanf("%d",&x);
dis[x]=0ll;
pq.push({0,x});
}
dij();
for(int u=1;u<=n;u++)
for(auto e:adj[u]){
int v = e.first;
ll w = min(dis[u],dis[v]);
edges.push_back( { w , { u , v } } );
}
sort(edges.begin(),edges.end());
reverse(edges.begin(),edges.end());
for(auto e:edges){
int u = e.second.first;
int v = e.second.second;
if( get(u) == get(v) )continue;
mrg(u,v);
ADJ[u].push_back(v);
ADJ[v].push_back(u);
}
dfs(1,0);
cin>>Q;
while( Q-- ){
int u,v;
scanf("%d %d",&u,&v);
int k = LCA(u,v);
ll ans = min( f(u,dep[u]-dep[k]+1) , f(v,dep[v]-dep[k]+1) );
printf("%lld\n",ans);
}
}
int main(){
solve();
return 0;
}
Compilation message
plan.cpp: In function 'void solve()':
plan.cpp:116:10: 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:123:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&x);
~~~~~^~~~~~~~~
plan.cpp:153:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&u,&v);
~~~~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4988 KB |
Output is correct |
2 |
Correct |
7 ms |
5368 KB |
Output is correct |
3 |
Correct |
7 ms |
5368 KB |
Output is correct |
4 |
Correct |
7 ms |
4984 KB |
Output is correct |
5 |
Correct |
9 ms |
5368 KB |
Output is correct |
6 |
Correct |
8 ms |
5372 KB |
Output is correct |
7 |
Correct |
6 ms |
5112 KB |
Output is correct |
8 |
Correct |
6 ms |
5112 KB |
Output is correct |
9 |
Correct |
8 ms |
5368 KB |
Output is correct |
10 |
Correct |
8 ms |
5368 KB |
Output is correct |
11 |
Correct |
8 ms |
5368 KB |
Output is correct |
12 |
Correct |
7 ms |
5364 KB |
Output is correct |
13 |
Correct |
8 ms |
5368 KB |
Output is correct |
14 |
Correct |
7 ms |
5368 KB |
Output is correct |
15 |
Correct |
7 ms |
5368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4988 KB |
Output is correct |
2 |
Correct |
7 ms |
5368 KB |
Output is correct |
3 |
Correct |
7 ms |
5368 KB |
Output is correct |
4 |
Correct |
7 ms |
4984 KB |
Output is correct |
5 |
Correct |
9 ms |
5368 KB |
Output is correct |
6 |
Correct |
8 ms |
5372 KB |
Output is correct |
7 |
Correct |
6 ms |
5112 KB |
Output is correct |
8 |
Correct |
6 ms |
5112 KB |
Output is correct |
9 |
Correct |
8 ms |
5368 KB |
Output is correct |
10 |
Correct |
8 ms |
5368 KB |
Output is correct |
11 |
Correct |
8 ms |
5368 KB |
Output is correct |
12 |
Correct |
7 ms |
5364 KB |
Output is correct |
13 |
Correct |
8 ms |
5368 KB |
Output is correct |
14 |
Correct |
7 ms |
5368 KB |
Output is correct |
15 |
Correct |
7 ms |
5368 KB |
Output is correct |
16 |
Correct |
262 ms |
31536 KB |
Output is correct |
17 |
Correct |
900 ms |
60580 KB |
Output is correct |
18 |
Correct |
62 ms |
11240 KB |
Output is correct |
19 |
Correct |
221 ms |
39676 KB |
Output is correct |
20 |
Correct |
833 ms |
60476 KB |
Output is correct |
21 |
Correct |
424 ms |
43088 KB |
Output is correct |
22 |
Correct |
342 ms |
41440 KB |
Output is correct |
23 |
Correct |
852 ms |
60536 KB |
Output is correct |
24 |
Correct |
848 ms |
60632 KB |
Output is correct |
25 |
Correct |
871 ms |
60460 KB |
Output is correct |
26 |
Correct |
223 ms |
39396 KB |
Output is correct |
27 |
Correct |
224 ms |
39360 KB |
Output is correct |
28 |
Correct |
224 ms |
39520 KB |
Output is correct |
29 |
Correct |
221 ms |
39404 KB |
Output is correct |
30 |
Correct |
237 ms |
39648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
6 ms |
5112 KB |
Output is correct |
3 |
Correct |
6 ms |
5112 KB |
Output is correct |
4 |
Correct |
6 ms |
4984 KB |
Output is correct |
5 |
Correct |
6 ms |
5072 KB |
Output is correct |
6 |
Correct |
6 ms |
5084 KB |
Output is correct |
7 |
Correct |
6 ms |
5112 KB |
Output is correct |
8 |
Correct |
6 ms |
4984 KB |
Output is correct |
9 |
Correct |
6 ms |
4984 KB |
Output is correct |
10 |
Correct |
6 ms |
4984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
364 ms |
42668 KB |
Output is correct |
2 |
Correct |
748 ms |
59936 KB |
Output is correct |
3 |
Correct |
769 ms |
59932 KB |
Output is correct |
4 |
Correct |
197 ms |
38880 KB |
Output is correct |
5 |
Correct |
805 ms |
60008 KB |
Output is correct |
6 |
Correct |
779 ms |
59996 KB |
Output is correct |
7 |
Correct |
760 ms |
60036 KB |
Output is correct |
8 |
Correct |
765 ms |
59936 KB |
Output is correct |
9 |
Correct |
812 ms |
59956 KB |
Output is correct |
10 |
Correct |
808 ms |
59968 KB |
Output is correct |
11 |
Correct |
792 ms |
59988 KB |
Output is correct |
12 |
Correct |
773 ms |
59976 KB |
Output is correct |
13 |
Correct |
783 ms |
60048 KB |
Output is correct |
14 |
Correct |
789 ms |
59976 KB |
Output is correct |
15 |
Correct |
804 ms |
60120 KB |
Output is correct |
16 |
Correct |
810 ms |
60124 KB |
Output is correct |
17 |
Correct |
774 ms |
60052 KB |
Output is correct |
18 |
Correct |
768 ms |
59984 KB |
Output is correct |
19 |
Correct |
202 ms |
40436 KB |
Output is correct |
20 |
Correct |
791 ms |
60060 KB |
Output is correct |
21 |
Correct |
714 ms |
59424 KB |
Output is correct |
22 |
Correct |
166 ms |
39128 KB |
Output is correct |
23 |
Correct |
202 ms |
37012 KB |
Output is correct |
24 |
Correct |
167 ms |
39108 KB |
Output is correct |
25 |
Correct |
165 ms |
39388 KB |
Output is correct |
26 |
Correct |
215 ms |
37536 KB |
Output is correct |
27 |
Correct |
201 ms |
40160 KB |
Output is correct |
28 |
Correct |
179 ms |
39088 KB |
Output is correct |
29 |
Correct |
202 ms |
39544 KB |
Output is correct |
30 |
Correct |
166 ms |
39480 KB |
Output is correct |
31 |
Correct |
199 ms |
39616 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4988 KB |
Output is correct |
2 |
Correct |
7 ms |
5368 KB |
Output is correct |
3 |
Correct |
7 ms |
5368 KB |
Output is correct |
4 |
Correct |
7 ms |
4984 KB |
Output is correct |
5 |
Correct |
9 ms |
5368 KB |
Output is correct |
6 |
Correct |
8 ms |
5372 KB |
Output is correct |
7 |
Correct |
6 ms |
5112 KB |
Output is correct |
8 |
Correct |
6 ms |
5112 KB |
Output is correct |
9 |
Correct |
8 ms |
5368 KB |
Output is correct |
10 |
Correct |
8 ms |
5368 KB |
Output is correct |
11 |
Correct |
8 ms |
5368 KB |
Output is correct |
12 |
Correct |
7 ms |
5364 KB |
Output is correct |
13 |
Correct |
8 ms |
5368 KB |
Output is correct |
14 |
Correct |
7 ms |
5368 KB |
Output is correct |
15 |
Correct |
7 ms |
5368 KB |
Output is correct |
16 |
Correct |
262 ms |
31536 KB |
Output is correct |
17 |
Correct |
900 ms |
60580 KB |
Output is correct |
18 |
Correct |
62 ms |
11240 KB |
Output is correct |
19 |
Correct |
221 ms |
39676 KB |
Output is correct |
20 |
Correct |
833 ms |
60476 KB |
Output is correct |
21 |
Correct |
424 ms |
43088 KB |
Output is correct |
22 |
Correct |
342 ms |
41440 KB |
Output is correct |
23 |
Correct |
852 ms |
60536 KB |
Output is correct |
24 |
Correct |
848 ms |
60632 KB |
Output is correct |
25 |
Correct |
871 ms |
60460 KB |
Output is correct |
26 |
Correct |
223 ms |
39396 KB |
Output is correct |
27 |
Correct |
224 ms |
39360 KB |
Output is correct |
28 |
Correct |
224 ms |
39520 KB |
Output is correct |
29 |
Correct |
221 ms |
39404 KB |
Output is correct |
30 |
Correct |
237 ms |
39648 KB |
Output is correct |
31 |
Correct |
6 ms |
4984 KB |
Output is correct |
32 |
Correct |
6 ms |
5112 KB |
Output is correct |
33 |
Correct |
6 ms |
5112 KB |
Output is correct |
34 |
Correct |
6 ms |
4984 KB |
Output is correct |
35 |
Correct |
6 ms |
5072 KB |
Output is correct |
36 |
Correct |
6 ms |
5084 KB |
Output is correct |
37 |
Correct |
6 ms |
5112 KB |
Output is correct |
38 |
Correct |
6 ms |
4984 KB |
Output is correct |
39 |
Correct |
6 ms |
4984 KB |
Output is correct |
40 |
Correct |
6 ms |
4984 KB |
Output is correct |
41 |
Correct |
364 ms |
42668 KB |
Output is correct |
42 |
Correct |
748 ms |
59936 KB |
Output is correct |
43 |
Correct |
769 ms |
59932 KB |
Output is correct |
44 |
Correct |
197 ms |
38880 KB |
Output is correct |
45 |
Correct |
805 ms |
60008 KB |
Output is correct |
46 |
Correct |
779 ms |
59996 KB |
Output is correct |
47 |
Correct |
760 ms |
60036 KB |
Output is correct |
48 |
Correct |
765 ms |
59936 KB |
Output is correct |
49 |
Correct |
812 ms |
59956 KB |
Output is correct |
50 |
Correct |
808 ms |
59968 KB |
Output is correct |
51 |
Correct |
792 ms |
59988 KB |
Output is correct |
52 |
Correct |
773 ms |
59976 KB |
Output is correct |
53 |
Correct |
783 ms |
60048 KB |
Output is correct |
54 |
Correct |
789 ms |
59976 KB |
Output is correct |
55 |
Correct |
804 ms |
60120 KB |
Output is correct |
56 |
Correct |
810 ms |
60124 KB |
Output is correct |
57 |
Correct |
774 ms |
60052 KB |
Output is correct |
58 |
Correct |
768 ms |
59984 KB |
Output is correct |
59 |
Correct |
202 ms |
40436 KB |
Output is correct |
60 |
Correct |
791 ms |
60060 KB |
Output is correct |
61 |
Correct |
714 ms |
59424 KB |
Output is correct |
62 |
Correct |
166 ms |
39128 KB |
Output is correct |
63 |
Correct |
202 ms |
37012 KB |
Output is correct |
64 |
Correct |
167 ms |
39108 KB |
Output is correct |
65 |
Correct |
165 ms |
39388 KB |
Output is correct |
66 |
Correct |
215 ms |
37536 KB |
Output is correct |
67 |
Correct |
201 ms |
40160 KB |
Output is correct |
68 |
Correct |
179 ms |
39088 KB |
Output is correct |
69 |
Correct |
202 ms |
39544 KB |
Output is correct |
70 |
Correct |
166 ms |
39480 KB |
Output is correct |
71 |
Correct |
199 ms |
39616 KB |
Output is correct |
72 |
Correct |
468 ms |
43228 KB |
Output is correct |
73 |
Correct |
868 ms |
60668 KB |
Output is correct |
74 |
Correct |
882 ms |
60396 KB |
Output is correct |
75 |
Correct |
895 ms |
60460 KB |
Output is correct |
76 |
Correct |
902 ms |
60452 KB |
Output is correct |
77 |
Correct |
861 ms |
60544 KB |
Output is correct |
78 |
Correct |
886 ms |
60448 KB |
Output is correct |
79 |
Correct |
888 ms |
60464 KB |
Output is correct |
80 |
Correct |
953 ms |
60476 KB |
Output is correct |
81 |
Correct |
882 ms |
60392 KB |
Output is correct |
82 |
Correct |
872 ms |
60448 KB |
Output is correct |
83 |
Correct |
872 ms |
60536 KB |
Output is correct |
84 |
Correct |
933 ms |
60460 KB |
Output is correct |
85 |
Correct |
908 ms |
60448 KB |
Output is correct |
86 |
Correct |
869 ms |
60376 KB |
Output is correct |
87 |
Correct |
878 ms |
60404 KB |
Output is correct |
88 |
Correct |
893 ms |
60456 KB |
Output is correct |
89 |
Correct |
378 ms |
40444 KB |
Output is correct |
90 |
Correct |
900 ms |
60464 KB |
Output is correct |
91 |
Correct |
792 ms |
59740 KB |
Output is correct |
92 |
Correct |
233 ms |
39772 KB |
Output is correct |
93 |
Correct |
313 ms |
38036 KB |
Output is correct |
94 |
Correct |
232 ms |
39512 KB |
Output is correct |
95 |
Correct |
234 ms |
39520 KB |
Output is correct |
96 |
Correct |
328 ms |
37904 KB |
Output is correct |
97 |
Correct |
368 ms |
39740 KB |
Output is correct |
98 |
Correct |
239 ms |
39584 KB |
Output is correct |
99 |
Correct |
356 ms |
40720 KB |
Output is correct |
100 |
Correct |
230 ms |
39516 KB |
Output is correct |