#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define up_b upper_bound
#define low_b lower_bound
#define sz(x) (int)x.size()
#define all(v) v.begin(),v.end()
#define boost ios_base::sync_with_stdio(0),cin.tie(0),cout.tie()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef pair<ll,ll> pll;
const ll INF = 1e18;
const ll inf = 1e9;
const int mod = 1e9+7;
const int pi = acos(-1);
const int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1};
const int dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};
const int N = 1e5+5;
const int MAXN = 4e6+1;
vector<pii>g[N];
vector<int>gr[N];
int d[N],par[N],timer,tin[N],tout[N],up[N][22],mn[N][22];
int lvl[N];
int get(int v){
return v==par[v]?v:(par[v]=get(par[v]));
}
bool merge(int x,int y){
x=get(x);
y=get(y);
if(x==y)return 0;
else{
par[y]=x;
return 1;
}
}
void dfs(int v,int p){
tin[v]=++timer;
lvl[v]=lvl[p]+1;
up[v][0]=p;
mn[v][0]=min(d[v],d[p]);
for(int i=1;i<=19;i++){
up[v][i]=up[up[v][i-1]][i-1];
mn[v][i]=min(mn[v][i-1],mn[up[v][i-1]][i-1]);
}
for(int i=0;i<sz(gr[v]);i++){
int to=gr[v][i];
if(to!=p)dfs(to,v);
}
tout[v]=timer;
}
bool upper(int a,int b){
return tin[a]<=tin[b]&&tout[a]>=tout[b];
}
int lca(int a,int b){
if(upper(a,b))return a;
if(upper(b,a))return b;
for(int i=19;i>=0;i--){
if(!upper(up[a][i],b)){
a=up[a][i];
}
}
return up[a][0];
}
int get(int a,int dist){
if(dist==0)return d[a];
int res=d[a];
for(int i=0;dist;i++,dist/=2){
if(dist&1){
res=min(res,mn[a][i]);
a=up[a][i];
}
}
return res;
}
int getmin(int a,int b){
int l=lca(a,b);
int res1=get(a,lvl[a]-lvl[l]),res2=get(b,lvl[b]-lvl[l]);
//cout<<res1<<" "<<res2<<endl;
return min(res1,res2);
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
g[u].pb(mp(v,w));
g[v].pb(mp(u,w));
}
int k;
cin>>k;
for(int i=1;i<=n;i++){
d[i]=inf;
}
set<pii>s;
for(int i=1;i<=k;i++){
int x;
cin>>x;
d[x]=0;
s.insert(mp(0,x));
}
while(!s.empty()){
pii p=*s.begin();
s.erase(p);
int v=p.y;
for(int i=0;i<sz(g[v]);i++){
int to=g[v][i].x;
if(d[to]>d[v]+g[v][i].y){
s.erase(mp(d[to],to));
d[to]=d[v]+g[v][i].y;
s.insert(mp(d[to],to));
}
}
}
for(int i=1;i<=n;i++){
//cout<<d[i]<<" ";
par[i]=i;
}
vector< pair<int,pii> >edg;
for(int i=1;i<=n;i++){
for(int j=0;j<sz(g[i]);j++){
int to=g[i][j].x;
if(to>i){
//cout<<i<<" "<<to<<" "<<min(d[i],d[to])<<endl;
edg.pb(mp(min(d[i],d[to]),mp(i,to)));
}
}
}
sort(all(edg));
for(int i=sz(edg)-1;i>=0;i--){
int a=edg[i].y.x;
int b=edg[i].y.y;
if(merge(a,b)){
//cout<<a<<" "<<b<<endl;
gr[a].pb(b);
gr[b].pb(a);
}
}
dfs(1,1);
int q;
cin>>q;
while(q--){
int a,b;
cin>>a>>b;
cout<<getmin(a,b)<<endl;
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
11 ms |
5368 KB |
Output is correct |
3 |
Correct |
12 ms |
5368 KB |
Output is correct |
4 |
Correct |
6 ms |
4984 KB |
Output is correct |
5 |
Correct |
11 ms |
5368 KB |
Output is correct |
6 |
Correct |
11 ms |
5368 KB |
Output is correct |
7 |
Correct |
6 ms |
5112 KB |
Output is correct |
8 |
Correct |
6 ms |
5112 KB |
Output is correct |
9 |
Correct |
12 ms |
5368 KB |
Output is correct |
10 |
Correct |
12 ms |
5240 KB |
Output is correct |
11 |
Correct |
12 ms |
5404 KB |
Output is correct |
12 |
Correct |
11 ms |
5368 KB |
Output is correct |
13 |
Correct |
12 ms |
5240 KB |
Output is correct |
14 |
Correct |
11 ms |
5368 KB |
Output is correct |
15 |
Correct |
12 ms |
5368 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
11 ms |
5368 KB |
Output is correct |
3 |
Correct |
12 ms |
5368 KB |
Output is correct |
4 |
Correct |
6 ms |
4984 KB |
Output is correct |
5 |
Correct |
11 ms |
5368 KB |
Output is correct |
6 |
Correct |
11 ms |
5368 KB |
Output is correct |
7 |
Correct |
6 ms |
5112 KB |
Output is correct |
8 |
Correct |
6 ms |
5112 KB |
Output is correct |
9 |
Correct |
12 ms |
5368 KB |
Output is correct |
10 |
Correct |
12 ms |
5240 KB |
Output is correct |
11 |
Correct |
12 ms |
5404 KB |
Output is correct |
12 |
Correct |
11 ms |
5368 KB |
Output is correct |
13 |
Correct |
12 ms |
5240 KB |
Output is correct |
14 |
Correct |
11 ms |
5368 KB |
Output is correct |
15 |
Correct |
12 ms |
5368 KB |
Output is correct |
16 |
Correct |
742 ms |
27420 KB |
Output is correct |
17 |
Correct |
1827 ms |
46468 KB |
Output is correct |
18 |
Correct |
132 ms |
9464 KB |
Output is correct |
19 |
Correct |
691 ms |
33336 KB |
Output is correct |
20 |
Correct |
1815 ms |
46320 KB |
Output is correct |
21 |
Correct |
1039 ms |
35908 KB |
Output is correct |
22 |
Correct |
725 ms |
37232 KB |
Output is correct |
23 |
Correct |
1777 ms |
46408 KB |
Output is correct |
24 |
Correct |
1783 ms |
46320 KB |
Output is correct |
25 |
Correct |
1812 ms |
46252 KB |
Output is correct |
26 |
Correct |
676 ms |
33136 KB |
Output is correct |
27 |
Correct |
683 ms |
33292 KB |
Output is correct |
28 |
Correct |
679 ms |
33024 KB |
Output is correct |
29 |
Correct |
674 ms |
33180 KB |
Output is correct |
30 |
Correct |
672 ms |
33292 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
6 ms |
4984 KB |
Output is correct |
3 |
Correct |
6 ms |
4984 KB |
Output is correct |
4 |
Correct |
7 ms |
4984 KB |
Output is correct |
5 |
Correct |
6 ms |
4984 KB |
Output is correct |
6 |
Correct |
6 ms |
5084 KB |
Output is correct |
7 |
Correct |
6 ms |
5012 KB |
Output is correct |
8 |
Correct |
6 ms |
4984 KB |
Output is correct |
9 |
Correct |
6 ms |
5088 KB |
Output is correct |
10 |
Correct |
6 ms |
4984 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
624 ms |
35416 KB |
Output is correct |
2 |
Correct |
1343 ms |
46904 KB |
Output is correct |
3 |
Correct |
1331 ms |
47156 KB |
Output is correct |
4 |
Correct |
298 ms |
35324 KB |
Output is correct |
5 |
Correct |
1355 ms |
46824 KB |
Output is correct |
6 |
Correct |
1353 ms |
47044 KB |
Output is correct |
7 |
Correct |
1328 ms |
46712 KB |
Output is correct |
8 |
Correct |
1416 ms |
46808 KB |
Output is correct |
9 |
Correct |
1343 ms |
46568 KB |
Output is correct |
10 |
Correct |
1337 ms |
46748 KB |
Output is correct |
11 |
Correct |
1339 ms |
46232 KB |
Output is correct |
12 |
Correct |
1391 ms |
46564 KB |
Output is correct |
13 |
Correct |
1327 ms |
46556 KB |
Output is correct |
14 |
Correct |
1342 ms |
46416 KB |
Output is correct |
15 |
Correct |
1350 ms |
46712 KB |
Output is correct |
16 |
Correct |
1415 ms |
46504 KB |
Output is correct |
17 |
Correct |
1326 ms |
46504 KB |
Output is correct |
18 |
Correct |
1356 ms |
46592 KB |
Output is correct |
19 |
Correct |
316 ms |
36840 KB |
Output is correct |
20 |
Correct |
1385 ms |
46708 KB |
Output is correct |
21 |
Correct |
1298 ms |
46368 KB |
Output is correct |
22 |
Correct |
282 ms |
33476 KB |
Output is correct |
23 |
Correct |
300 ms |
33216 KB |
Output is correct |
24 |
Correct |
286 ms |
33444 KB |
Output is correct |
25 |
Correct |
318 ms |
33216 KB |
Output is correct |
26 |
Correct |
330 ms |
33488 KB |
Output is correct |
27 |
Correct |
304 ms |
36204 KB |
Output is correct |
28 |
Correct |
300 ms |
33148 KB |
Output is correct |
29 |
Correct |
304 ms |
35228 KB |
Output is correct |
30 |
Correct |
289 ms |
32828 KB |
Output is correct |
31 |
Correct |
300 ms |
35176 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
11 ms |
5368 KB |
Output is correct |
3 |
Correct |
12 ms |
5368 KB |
Output is correct |
4 |
Correct |
6 ms |
4984 KB |
Output is correct |
5 |
Correct |
11 ms |
5368 KB |
Output is correct |
6 |
Correct |
11 ms |
5368 KB |
Output is correct |
7 |
Correct |
6 ms |
5112 KB |
Output is correct |
8 |
Correct |
6 ms |
5112 KB |
Output is correct |
9 |
Correct |
12 ms |
5368 KB |
Output is correct |
10 |
Correct |
12 ms |
5240 KB |
Output is correct |
11 |
Correct |
12 ms |
5404 KB |
Output is correct |
12 |
Correct |
11 ms |
5368 KB |
Output is correct |
13 |
Correct |
12 ms |
5240 KB |
Output is correct |
14 |
Correct |
11 ms |
5368 KB |
Output is correct |
15 |
Correct |
12 ms |
5368 KB |
Output is correct |
16 |
Correct |
742 ms |
27420 KB |
Output is correct |
17 |
Correct |
1827 ms |
46468 KB |
Output is correct |
18 |
Correct |
132 ms |
9464 KB |
Output is correct |
19 |
Correct |
691 ms |
33336 KB |
Output is correct |
20 |
Correct |
1815 ms |
46320 KB |
Output is correct |
21 |
Correct |
1039 ms |
35908 KB |
Output is correct |
22 |
Correct |
725 ms |
37232 KB |
Output is correct |
23 |
Correct |
1777 ms |
46408 KB |
Output is correct |
24 |
Correct |
1783 ms |
46320 KB |
Output is correct |
25 |
Correct |
1812 ms |
46252 KB |
Output is correct |
26 |
Correct |
676 ms |
33136 KB |
Output is correct |
27 |
Correct |
683 ms |
33292 KB |
Output is correct |
28 |
Correct |
679 ms |
33024 KB |
Output is correct |
29 |
Correct |
674 ms |
33180 KB |
Output is correct |
30 |
Correct |
672 ms |
33292 KB |
Output is correct |
31 |
Correct |
6 ms |
4984 KB |
Output is correct |
32 |
Correct |
6 ms |
4984 KB |
Output is correct |
33 |
Correct |
6 ms |
4984 KB |
Output is correct |
34 |
Correct |
7 ms |
4984 KB |
Output is correct |
35 |
Correct |
6 ms |
4984 KB |
Output is correct |
36 |
Correct |
6 ms |
5084 KB |
Output is correct |
37 |
Correct |
6 ms |
5012 KB |
Output is correct |
38 |
Correct |
6 ms |
4984 KB |
Output is correct |
39 |
Correct |
6 ms |
5088 KB |
Output is correct |
40 |
Correct |
6 ms |
4984 KB |
Output is correct |
41 |
Correct |
624 ms |
35416 KB |
Output is correct |
42 |
Correct |
1343 ms |
46904 KB |
Output is correct |
43 |
Correct |
1331 ms |
47156 KB |
Output is correct |
44 |
Correct |
298 ms |
35324 KB |
Output is correct |
45 |
Correct |
1355 ms |
46824 KB |
Output is correct |
46 |
Correct |
1353 ms |
47044 KB |
Output is correct |
47 |
Correct |
1328 ms |
46712 KB |
Output is correct |
48 |
Correct |
1416 ms |
46808 KB |
Output is correct |
49 |
Correct |
1343 ms |
46568 KB |
Output is correct |
50 |
Correct |
1337 ms |
46748 KB |
Output is correct |
51 |
Correct |
1339 ms |
46232 KB |
Output is correct |
52 |
Correct |
1391 ms |
46564 KB |
Output is correct |
53 |
Correct |
1327 ms |
46556 KB |
Output is correct |
54 |
Correct |
1342 ms |
46416 KB |
Output is correct |
55 |
Correct |
1350 ms |
46712 KB |
Output is correct |
56 |
Correct |
1415 ms |
46504 KB |
Output is correct |
57 |
Correct |
1326 ms |
46504 KB |
Output is correct |
58 |
Correct |
1356 ms |
46592 KB |
Output is correct |
59 |
Correct |
316 ms |
36840 KB |
Output is correct |
60 |
Correct |
1385 ms |
46708 KB |
Output is correct |
61 |
Correct |
1298 ms |
46368 KB |
Output is correct |
62 |
Correct |
282 ms |
33476 KB |
Output is correct |
63 |
Correct |
300 ms |
33216 KB |
Output is correct |
64 |
Correct |
286 ms |
33444 KB |
Output is correct |
65 |
Correct |
318 ms |
33216 KB |
Output is correct |
66 |
Correct |
330 ms |
33488 KB |
Output is correct |
67 |
Correct |
304 ms |
36204 KB |
Output is correct |
68 |
Correct |
300 ms |
33148 KB |
Output is correct |
69 |
Correct |
304 ms |
35228 KB |
Output is correct |
70 |
Correct |
289 ms |
32828 KB |
Output is correct |
71 |
Correct |
300 ms |
35176 KB |
Output is correct |
72 |
Correct |
1067 ms |
36112 KB |
Output is correct |
73 |
Correct |
1785 ms |
46296 KB |
Output is correct |
74 |
Correct |
1861 ms |
46516 KB |
Output is correct |
75 |
Correct |
1805 ms |
46384 KB |
Output is correct |
76 |
Correct |
1818 ms |
46348 KB |
Output is correct |
77 |
Correct |
1836 ms |
46388 KB |
Output is correct |
78 |
Correct |
1836 ms |
46380 KB |
Output is correct |
79 |
Correct |
1833 ms |
46348 KB |
Output is correct |
80 |
Correct |
1794 ms |
46432 KB |
Output is correct |
81 |
Correct |
1794 ms |
46368 KB |
Output is correct |
82 |
Correct |
1812 ms |
46412 KB |
Output is correct |
83 |
Correct |
1827 ms |
46448 KB |
Output is correct |
84 |
Correct |
1818 ms |
46364 KB |
Output is correct |
85 |
Correct |
1822 ms |
46216 KB |
Output is correct |
86 |
Correct |
1842 ms |
46436 KB |
Output is correct |
87 |
Correct |
1950 ms |
46296 KB |
Output is correct |
88 |
Correct |
1804 ms |
46328 KB |
Output is correct |
89 |
Correct |
805 ms |
36104 KB |
Output is correct |
90 |
Correct |
1806 ms |
46308 KB |
Output is correct |
91 |
Correct |
1705 ms |
46380 KB |
Output is correct |
92 |
Correct |
711 ms |
33172 KB |
Output is correct |
93 |
Correct |
808 ms |
33648 KB |
Output is correct |
94 |
Correct |
709 ms |
33148 KB |
Output is correct |
95 |
Correct |
707 ms |
33172 KB |
Output is correct |
96 |
Correct |
791 ms |
33012 KB |
Output is correct |
97 |
Correct |
806 ms |
35332 KB |
Output is correct |
98 |
Correct |
766 ms |
33128 KB |
Output is correct |
99 |
Correct |
815 ms |
36420 KB |
Output is correct |
100 |
Correct |
728 ms |
33152 KB |
Output is correct |