#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
const ll inf=1e15;
#define pb push_back
const int INF=(0x3f3f3f3f);
int n,m,par[N],sz[N],k,up[20][N];
ll mn[20][N],tin[N],tout[N],timer;
ll dist[N];
vector<pair<int,ll>>g[N];
vector<pair<int,int>>road;
int find(int a){
if(a==par[a])return a;
return par[a]=find(par[a]);
}
void merge(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 p,ll w){
up[0][v]=p;
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.first!=p)dfs(to.first,v,to.second);
tout[v]=++timer;
}
bool upper(int a,int b){
return tin[a]<=tin[b]&&tout[a]>=tout[b];
}
ll get(int a,int b){
ll 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;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){par[i]=i;sz[i]=1;}
for(int i=0;i<m;i++){
int a,b;ll c;
cin>>a>>b>>c;
g[a].pb({b,c});
g[b].pb({a,c});
road.pb({a,b});
}
priority_queue<pair<ll,int>> q;
cin>>k;
memset(dist,0x3f3f3f3f,sizeof(dist));
for(int i=0;i<k;i++){
int v;cin>>v;
dist[v]=0;q.push({0,v});
}
while(!q.empty()){
int v=q.top().second;
q.pop();
for(auto x:g[v]){
if(dist[x.first]>dist[v]+x.second){
dist[x.first]=dist[v]+x.second;
q.push({-dist[x.first],x.first});
}
}
}
for(int i=1;i<=n;i++)g[i].clear();
vector<pair<ll,pair<int,int>>> vec;
for(int i=0;i<m;i++)
vec.pb({min(dist[road[i].first],dist[road[i].second]),{road[i].first,road[i].second}});
sort(vec.begin(),vec.end());
reverse(vec.begin(),vec.end());
for(int i=0;i<m;i++){
int a=vec[i].second.first,b=vec[i].second.second;
ll w=min(dist[a],dist[b]);
if(find(a)!=find(b)){
g[a].pb({b,w});
g[b].pb({a,w});
merge(a,b);
}
}
dfs(1,1,INF);
int Q;
cin>>Q;
for(int i=0;i<Q;i++){
int a,b;
cin>>a>>b;
cout<<get(a,b)<<'\n';
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
3704 KB |
Output is correct |
2 |
Correct |
6 ms |
4088 KB |
Output is correct |
3 |
Correct |
5 ms |
4088 KB |
Output is correct |
4 |
Correct |
5 ms |
3704 KB |
Output is correct |
5 |
Correct |
6 ms |
4088 KB |
Output is correct |
6 |
Correct |
7 ms |
4112 KB |
Output is correct |
7 |
Correct |
5 ms |
3704 KB |
Output is correct |
8 |
Correct |
6 ms |
3704 KB |
Output is correct |
9 |
Correct |
9 ms |
4088 KB |
Output is correct |
10 |
Correct |
7 ms |
4124 KB |
Output is correct |
11 |
Correct |
6 ms |
4088 KB |
Output is correct |
12 |
Correct |
16 ms |
4116 KB |
Output is correct |
13 |
Correct |
5 ms |
4064 KB |
Output is correct |
14 |
Correct |
7 ms |
4060 KB |
Output is correct |
15 |
Correct |
7 ms |
4216 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
3704 KB |
Output is correct |
2 |
Correct |
6 ms |
4088 KB |
Output is correct |
3 |
Correct |
5 ms |
4088 KB |
Output is correct |
4 |
Correct |
5 ms |
3704 KB |
Output is correct |
5 |
Correct |
6 ms |
4088 KB |
Output is correct |
6 |
Correct |
7 ms |
4112 KB |
Output is correct |
7 |
Correct |
5 ms |
3704 KB |
Output is correct |
8 |
Correct |
6 ms |
3704 KB |
Output is correct |
9 |
Correct |
9 ms |
4088 KB |
Output is correct |
10 |
Correct |
7 ms |
4124 KB |
Output is correct |
11 |
Correct |
6 ms |
4088 KB |
Output is correct |
12 |
Correct |
16 ms |
4116 KB |
Output is correct |
13 |
Correct |
5 ms |
4064 KB |
Output is correct |
14 |
Correct |
7 ms |
4060 KB |
Output is correct |
15 |
Correct |
7 ms |
4216 KB |
Output is correct |
16 |
Correct |
378 ms |
36244 KB |
Output is correct |
17 |
Correct |
896 ms |
80144 KB |
Output is correct |
18 |
Correct |
58 ms |
11472 KB |
Output is correct |
19 |
Correct |
251 ms |
41384 KB |
Output is correct |
20 |
Correct |
875 ms |
80308 KB |
Output is correct |
21 |
Correct |
491 ms |
51156 KB |
Output is correct |
22 |
Correct |
300 ms |
44872 KB |
Output is correct |
23 |
Correct |
889 ms |
81984 KB |
Output is correct |
24 |
Correct |
844 ms |
80616 KB |
Output is correct |
25 |
Correct |
855 ms |
80692 KB |
Output is correct |
26 |
Correct |
235 ms |
41152 KB |
Output is correct |
27 |
Correct |
229 ms |
41316 KB |
Output is correct |
28 |
Correct |
243 ms |
41196 KB |
Output is correct |
29 |
Correct |
233 ms |
41204 KB |
Output is correct |
30 |
Correct |
272 ms |
41400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
3672 KB |
Output is correct |
2 |
Correct |
5 ms |
3716 KB |
Output is correct |
3 |
Correct |
5 ms |
3704 KB |
Output is correct |
4 |
Correct |
5 ms |
3704 KB |
Output is correct |
5 |
Correct |
5 ms |
3704 KB |
Output is correct |
6 |
Correct |
5 ms |
3704 KB |
Output is correct |
7 |
Correct |
5 ms |
3704 KB |
Output is correct |
8 |
Correct |
5 ms |
3640 KB |
Output is correct |
9 |
Correct |
5 ms |
3704 KB |
Output is correct |
10 |
Correct |
5 ms |
3628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
396 ms |
50140 KB |
Output is correct |
2 |
Correct |
746 ms |
76412 KB |
Output is correct |
3 |
Correct |
758 ms |
77100 KB |
Output is correct |
4 |
Correct |
232 ms |
40984 KB |
Output is correct |
5 |
Correct |
746 ms |
76092 KB |
Output is correct |
6 |
Correct |
748 ms |
76872 KB |
Output is correct |
7 |
Correct |
746 ms |
75776 KB |
Output is correct |
8 |
Correct |
759 ms |
75820 KB |
Output is correct |
9 |
Correct |
748 ms |
76924 KB |
Output is correct |
10 |
Correct |
735 ms |
75872 KB |
Output is correct |
11 |
Correct |
733 ms |
75564 KB |
Output is correct |
12 |
Correct |
730 ms |
75308 KB |
Output is correct |
13 |
Correct |
740 ms |
76200 KB |
Output is correct |
14 |
Correct |
750 ms |
76764 KB |
Output is correct |
15 |
Correct |
756 ms |
72336 KB |
Output is correct |
16 |
Correct |
749 ms |
76984 KB |
Output is correct |
17 |
Correct |
728 ms |
76604 KB |
Output is correct |
18 |
Correct |
732 ms |
77064 KB |
Output is correct |
19 |
Correct |
227 ms |
42564 KB |
Output is correct |
20 |
Correct |
729 ms |
77540 KB |
Output is correct |
21 |
Correct |
681 ms |
77728 KB |
Output is correct |
22 |
Correct |
161 ms |
39664 KB |
Output is correct |
23 |
Correct |
216 ms |
39020 KB |
Output is correct |
24 |
Correct |
165 ms |
39724 KB |
Output is correct |
25 |
Correct |
166 ms |
39752 KB |
Output is correct |
26 |
Correct |
238 ms |
40368 KB |
Output is correct |
27 |
Correct |
225 ms |
42380 KB |
Output is correct |
28 |
Correct |
170 ms |
39724 KB |
Output is correct |
29 |
Correct |
233 ms |
41684 KB |
Output is correct |
30 |
Correct |
167 ms |
39644 KB |
Output is correct |
31 |
Correct |
231 ms |
41756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
3704 KB |
Output is correct |
2 |
Correct |
6 ms |
4088 KB |
Output is correct |
3 |
Correct |
5 ms |
4088 KB |
Output is correct |
4 |
Correct |
5 ms |
3704 KB |
Output is correct |
5 |
Correct |
6 ms |
4088 KB |
Output is correct |
6 |
Correct |
7 ms |
4112 KB |
Output is correct |
7 |
Correct |
5 ms |
3704 KB |
Output is correct |
8 |
Correct |
6 ms |
3704 KB |
Output is correct |
9 |
Correct |
9 ms |
4088 KB |
Output is correct |
10 |
Correct |
7 ms |
4124 KB |
Output is correct |
11 |
Correct |
6 ms |
4088 KB |
Output is correct |
12 |
Correct |
16 ms |
4116 KB |
Output is correct |
13 |
Correct |
5 ms |
4064 KB |
Output is correct |
14 |
Correct |
7 ms |
4060 KB |
Output is correct |
15 |
Correct |
7 ms |
4216 KB |
Output is correct |
16 |
Correct |
378 ms |
36244 KB |
Output is correct |
17 |
Correct |
896 ms |
80144 KB |
Output is correct |
18 |
Correct |
58 ms |
11472 KB |
Output is correct |
19 |
Correct |
251 ms |
41384 KB |
Output is correct |
20 |
Correct |
875 ms |
80308 KB |
Output is correct |
21 |
Correct |
491 ms |
51156 KB |
Output is correct |
22 |
Correct |
300 ms |
44872 KB |
Output is correct |
23 |
Correct |
889 ms |
81984 KB |
Output is correct |
24 |
Correct |
844 ms |
80616 KB |
Output is correct |
25 |
Correct |
855 ms |
80692 KB |
Output is correct |
26 |
Correct |
235 ms |
41152 KB |
Output is correct |
27 |
Correct |
229 ms |
41316 KB |
Output is correct |
28 |
Correct |
243 ms |
41196 KB |
Output is correct |
29 |
Correct |
233 ms |
41204 KB |
Output is correct |
30 |
Correct |
272 ms |
41400 KB |
Output is correct |
31 |
Correct |
5 ms |
3672 KB |
Output is correct |
32 |
Correct |
5 ms |
3716 KB |
Output is correct |
33 |
Correct |
5 ms |
3704 KB |
Output is correct |
34 |
Correct |
5 ms |
3704 KB |
Output is correct |
35 |
Correct |
5 ms |
3704 KB |
Output is correct |
36 |
Correct |
5 ms |
3704 KB |
Output is correct |
37 |
Correct |
5 ms |
3704 KB |
Output is correct |
38 |
Correct |
5 ms |
3640 KB |
Output is correct |
39 |
Correct |
5 ms |
3704 KB |
Output is correct |
40 |
Correct |
5 ms |
3628 KB |
Output is correct |
41 |
Correct |
396 ms |
50140 KB |
Output is correct |
42 |
Correct |
746 ms |
76412 KB |
Output is correct |
43 |
Correct |
758 ms |
77100 KB |
Output is correct |
44 |
Correct |
232 ms |
40984 KB |
Output is correct |
45 |
Correct |
746 ms |
76092 KB |
Output is correct |
46 |
Correct |
748 ms |
76872 KB |
Output is correct |
47 |
Correct |
746 ms |
75776 KB |
Output is correct |
48 |
Correct |
759 ms |
75820 KB |
Output is correct |
49 |
Correct |
748 ms |
76924 KB |
Output is correct |
50 |
Correct |
735 ms |
75872 KB |
Output is correct |
51 |
Correct |
733 ms |
75564 KB |
Output is correct |
52 |
Correct |
730 ms |
75308 KB |
Output is correct |
53 |
Correct |
740 ms |
76200 KB |
Output is correct |
54 |
Correct |
750 ms |
76764 KB |
Output is correct |
55 |
Correct |
756 ms |
72336 KB |
Output is correct |
56 |
Correct |
749 ms |
76984 KB |
Output is correct |
57 |
Correct |
728 ms |
76604 KB |
Output is correct |
58 |
Correct |
732 ms |
77064 KB |
Output is correct |
59 |
Correct |
227 ms |
42564 KB |
Output is correct |
60 |
Correct |
729 ms |
77540 KB |
Output is correct |
61 |
Correct |
681 ms |
77728 KB |
Output is correct |
62 |
Correct |
161 ms |
39664 KB |
Output is correct |
63 |
Correct |
216 ms |
39020 KB |
Output is correct |
64 |
Correct |
165 ms |
39724 KB |
Output is correct |
65 |
Correct |
166 ms |
39752 KB |
Output is correct |
66 |
Correct |
238 ms |
40368 KB |
Output is correct |
67 |
Correct |
225 ms |
42380 KB |
Output is correct |
68 |
Correct |
170 ms |
39724 KB |
Output is correct |
69 |
Correct |
233 ms |
41684 KB |
Output is correct |
70 |
Correct |
167 ms |
39644 KB |
Output is correct |
71 |
Correct |
231 ms |
41756 KB |
Output is correct |
72 |
Correct |
489 ms |
52868 KB |
Output is correct |
73 |
Correct |
853 ms |
80760 KB |
Output is correct |
74 |
Correct |
851 ms |
80116 KB |
Output is correct |
75 |
Correct |
815 ms |
80016 KB |
Output is correct |
76 |
Correct |
812 ms |
80532 KB |
Output is correct |
77 |
Correct |
844 ms |
79880 KB |
Output is correct |
78 |
Correct |
838 ms |
80340 KB |
Output is correct |
79 |
Correct |
802 ms |
79860 KB |
Output is correct |
80 |
Correct |
806 ms |
79664 KB |
Output is correct |
81 |
Correct |
823 ms |
80192 KB |
Output is correct |
82 |
Correct |
857 ms |
80144 KB |
Output is correct |
83 |
Correct |
828 ms |
81036 KB |
Output is correct |
84 |
Correct |
844 ms |
81192 KB |
Output is correct |
85 |
Correct |
850 ms |
76572 KB |
Output is correct |
86 |
Correct |
832 ms |
79908 KB |
Output is correct |
87 |
Correct |
837 ms |
79808 KB |
Output is correct |
88 |
Correct |
839 ms |
79168 KB |
Output is correct |
89 |
Correct |
402 ms |
43808 KB |
Output is correct |
90 |
Correct |
806 ms |
78788 KB |
Output is correct |
91 |
Correct |
789 ms |
77564 KB |
Output is correct |
92 |
Correct |
240 ms |
41068 KB |
Output is correct |
93 |
Correct |
364 ms |
40896 KB |
Output is correct |
94 |
Correct |
247 ms |
40920 KB |
Output is correct |
95 |
Correct |
240 ms |
41016 KB |
Output is correct |
96 |
Correct |
362 ms |
41352 KB |
Output is correct |
97 |
Correct |
402 ms |
41936 KB |
Output is correct |
98 |
Correct |
243 ms |
40668 KB |
Output is correct |
99 |
Correct |
405 ms |
43748 KB |
Output is correct |
100 |
Correct |
246 ms |
40916 KB |
Output is correct |