#include<bits/stdc++.h>
#define ll long long
const ll MAXN=100000;
const ll INF=1000000000000;
using namespace std;
vector < vector < ll > > dp(100005), dp_mn(100005);
vector < vector < pair < ll, ll > > > g(100005), tree(100005);
ll time_in[100005], time_out[100005], parent[100005], pat[100005];
ll n, m, timer, lg, rad, a, b;
vector < ll > dist;
set < pair < ll, pair < ll, ll > > > stk;
set < pair < ll, pair < ll, ll > > > ::iterator stk_it;
void make_set (ll);
ll find_set(ll);
void union_sets(ll,ll);
void DFS (ll,ll,ll);
ll get_min(ll,ll);
ll lca (ll,ll);
void sol();
bool issubtree (ll a, ll b) {
if (time_in[a]<=time_in[b] && time_out[b]<=time_out[a])
return true;
return false;
}
int main () {
ios_base::sync_with_stdio(false);
cin >> n >> m;
for (ll k=1; k<=m; k++) {
ll x, y, z;
cin >> x >> y >> z;
g[x].push_back({y,z});
g[y].push_back({x,z});
}
dist.resize(n+2,INF);
set < pair < ll, ll > > st;
cin >> rad;
for (ll k=1; k<=rad; k++) {
ll x;
cin >> x;
dist[x]=0;
st.insert({dist[x],x});
}
while (!st.empty()) {
ll v=(*st.begin()).second;
st.erase(st.begin());
for (ll k=0; k<g[v].size(); k++) {
ll to=g[v][k].first; ll price=g[v][k].second;
if (dist[to]>dist[v]+price) {
st.erase({dist[to],to});
dist[to]=dist[v]+price;
st.insert({dist[to],to});
}
}
}
for (ll k=1; k<=n; k++)
make_set(k);
for (ll k=1; k<=n; k++)
for (ll i=0; i<g[k].size(); i++) {
ll x=k; ll y=g[k][i].first;
g[k][i].second=min(dist[x],dist[y]);
stk.insert({-g[k][i].second,{x,y}});
}
while (!stk.empty()) {
stk_it=stk.begin();
a=stk_it->second.first;
b=stk_it->second.second;
while (find_set(a)==find_set(b)) {
stk.erase(stk_it);
if (stk.empty()) break;
stk_it=stk.begin();
a=stk_it->second.first;
b=stk_it->second.second;
}
if (stk.empty()) break;
union_sets(a,b);
ll price=stk_it->first;
tree[a].push_back(make_pair(b,-price));
tree[b].push_back(make_pair(a,-price));
stk.erase(stk_it);
}
lg=log2(n+1);
for (ll k=0; k<=n; k++) {
dp[k].resize(lg+1);
dp_mn[k].resize(lg+1);
}
DFS(1,0,INF);
ll Q;
cin >> Q;
while (Q--) {
ll a, b;
cin >> a >> b;
ll LCA=lca(a,b);
ll answer=min(get_min(a,LCA),get_min(b,LCA));
cout << answer << endl;
}
return 0;
}
void make_set (ll v) {
parent[v]=v;
}
ll find_set (ll v) {
if (v==parent[v])
return parent[v];
return parent[v]=find_set(parent[v]);
}
void union_sets (ll a, ll b) {
a=find_set(a);
b=find_set(b);
if (a!=b)
parent[b]=a;
}
void DFS (ll v, ll p, ll d) {
pat[v]=p;
dp[v][0]=p;
dp_mn[v][0]=d;
for (ll k=1; k<=lg; k++) {
dp[v][k]=dp[dp[v][k-1]][k-1];
if (dp[v][k]!=0)
dp_mn[v][k]=min(dp_mn[v][k-1],dp_mn[dp[v][k-1]][k-1]);
}
time_in[v]=timer++;
for (ll k=0; k<tree[v].size(); k++) {
ll to=tree[v][k].first;
if (to==p) continue;
DFS(to,v,tree[v][k].second);
}
time_out[v]=timer++;
}
ll lca (ll a, ll b) {
if (issubtree(a,b))
return a;
if (issubtree(b,a))
return b;
for (ll k=lg; k>=0; k--) {
if (dp[a][k]==0) continue;
if (issubtree(dp[a][k],b)) continue;
a=dp[a][k];
}
return pat[a];
}
ll get_min (ll a, ll LCA) {
ll counter=INF;
for (ll k=lg; k>=0; k--) {
if (dp[a][k]==0) continue;
if (issubtree(dp[a][k],LCA) && dp[a][k]!=LCA) continue;
counter=min(counter,dp_mn[a][k]);
a=dp[a][k];
}
return counter;
}
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/
Compilation message
plan.cpp: In function 'bool issubtree(long long int, long long int)':
plan.cpp:24:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if (time_in[a]<=time_in[b] && time_out[b]<=time_out[a])
^~
plan.cpp:27:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
return false;
^~~~~~
plan.cpp: In function 'int main()':
plan.cpp:57:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (ll k=0; k<g[v].size(); k++) {
~^~~~~~~~~~~~
plan.cpp:72:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (ll i=0; i<g[k].size(); i++) {
~^~~~~~~~~~~~
plan.cpp: In function 'void DFS(long long int, long long int, long long int)':
plan.cpp:161:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (ll k=0; k<tree[v].size(); k++) {
~^~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
9720 KB |
Output is correct |
2 |
Correct |
15 ms |
10104 KB |
Output is correct |
3 |
Correct |
15 ms |
10104 KB |
Output is correct |
4 |
Correct |
10 ms |
9720 KB |
Output is correct |
5 |
Correct |
15 ms |
10104 KB |
Output is correct |
6 |
Correct |
15 ms |
10104 KB |
Output is correct |
7 |
Correct |
10 ms |
9848 KB |
Output is correct |
8 |
Correct |
10 ms |
9848 KB |
Output is correct |
9 |
Correct |
16 ms |
10132 KB |
Output is correct |
10 |
Correct |
16 ms |
10104 KB |
Output is correct |
11 |
Correct |
16 ms |
10104 KB |
Output is correct |
12 |
Correct |
15 ms |
10104 KB |
Output is correct |
13 |
Correct |
16 ms |
10104 KB |
Output is correct |
14 |
Correct |
16 ms |
10180 KB |
Output is correct |
15 |
Correct |
15 ms |
10104 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
9720 KB |
Output is correct |
2 |
Correct |
15 ms |
10104 KB |
Output is correct |
3 |
Correct |
15 ms |
10104 KB |
Output is correct |
4 |
Correct |
10 ms |
9720 KB |
Output is correct |
5 |
Correct |
15 ms |
10104 KB |
Output is correct |
6 |
Correct |
15 ms |
10104 KB |
Output is correct |
7 |
Correct |
10 ms |
9848 KB |
Output is correct |
8 |
Correct |
10 ms |
9848 KB |
Output is correct |
9 |
Correct |
16 ms |
10132 KB |
Output is correct |
10 |
Correct |
16 ms |
10104 KB |
Output is correct |
11 |
Correct |
16 ms |
10104 KB |
Output is correct |
12 |
Correct |
15 ms |
10104 KB |
Output is correct |
13 |
Correct |
16 ms |
10104 KB |
Output is correct |
14 |
Correct |
16 ms |
10180 KB |
Output is correct |
15 |
Correct |
15 ms |
10104 KB |
Output is correct |
16 |
Correct |
831 ms |
47384 KB |
Output is correct |
17 |
Correct |
2373 ms |
102192 KB |
Output is correct |
18 |
Correct |
138 ms |
18168 KB |
Output is correct |
19 |
Correct |
704 ms |
55240 KB |
Output is correct |
20 |
Correct |
2305 ms |
102032 KB |
Output is correct |
21 |
Correct |
1080 ms |
61388 KB |
Output is correct |
22 |
Correct |
863 ms |
59544 KB |
Output is correct |
23 |
Correct |
2339 ms |
102448 KB |
Output is correct |
24 |
Correct |
2392 ms |
103052 KB |
Output is correct |
25 |
Correct |
2286 ms |
102788 KB |
Output is correct |
26 |
Correct |
737 ms |
54632 KB |
Output is correct |
27 |
Correct |
682 ms |
54456 KB |
Output is correct |
28 |
Correct |
664 ms |
53600 KB |
Output is correct |
29 |
Correct |
682 ms |
54612 KB |
Output is correct |
30 |
Correct |
702 ms |
54376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
9720 KB |
Output is correct |
2 |
Correct |
11 ms |
9720 KB |
Output is correct |
3 |
Correct |
13 ms |
9764 KB |
Output is correct |
4 |
Correct |
11 ms |
9720 KB |
Output is correct |
5 |
Correct |
11 ms |
9720 KB |
Output is correct |
6 |
Correct |
10 ms |
9720 KB |
Output is correct |
7 |
Correct |
11 ms |
9720 KB |
Output is correct |
8 |
Correct |
11 ms |
9720 KB |
Output is correct |
9 |
Correct |
10 ms |
9720 KB |
Output is correct |
10 |
Correct |
11 ms |
9720 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
837 ms |
60100 KB |
Output is correct |
2 |
Correct |
1897 ms |
99904 KB |
Output is correct |
3 |
Correct |
1958 ms |
99864 KB |
Output is correct |
4 |
Correct |
425 ms |
56004 KB |
Output is correct |
5 |
Correct |
1965 ms |
99928 KB |
Output is correct |
6 |
Correct |
1901 ms |
99860 KB |
Output is correct |
7 |
Correct |
1984 ms |
99964 KB |
Output is correct |
8 |
Correct |
1962 ms |
99872 KB |
Output is correct |
9 |
Correct |
1912 ms |
99996 KB |
Output is correct |
10 |
Correct |
1917 ms |
99872 KB |
Output is correct |
11 |
Correct |
1975 ms |
99860 KB |
Output is correct |
12 |
Correct |
1975 ms |
99940 KB |
Output is correct |
13 |
Correct |
1967 ms |
99868 KB |
Output is correct |
14 |
Correct |
1902 ms |
99900 KB |
Output is correct |
15 |
Correct |
1815 ms |
99860 KB |
Output is correct |
16 |
Correct |
1964 ms |
99856 KB |
Output is correct |
17 |
Correct |
2116 ms |
99868 KB |
Output is correct |
18 |
Correct |
1972 ms |
99828 KB |
Output is correct |
19 |
Correct |
452 ms |
57492 KB |
Output is correct |
20 |
Correct |
1920 ms |
100080 KB |
Output is correct |
21 |
Correct |
1118 ms |
100188 KB |
Output is correct |
22 |
Correct |
366 ms |
54032 KB |
Output is correct |
23 |
Correct |
438 ms |
54364 KB |
Output is correct |
24 |
Correct |
381 ms |
54312 KB |
Output is correct |
25 |
Correct |
351 ms |
54032 KB |
Output is correct |
26 |
Correct |
507 ms |
55460 KB |
Output is correct |
27 |
Correct |
494 ms |
58116 KB |
Output is correct |
28 |
Correct |
375 ms |
55104 KB |
Output is correct |
29 |
Correct |
455 ms |
57324 KB |
Output is correct |
30 |
Correct |
349 ms |
55372 KB |
Output is correct |
31 |
Correct |
466 ms |
57244 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
9720 KB |
Output is correct |
2 |
Correct |
15 ms |
10104 KB |
Output is correct |
3 |
Correct |
15 ms |
10104 KB |
Output is correct |
4 |
Correct |
10 ms |
9720 KB |
Output is correct |
5 |
Correct |
15 ms |
10104 KB |
Output is correct |
6 |
Correct |
15 ms |
10104 KB |
Output is correct |
7 |
Correct |
10 ms |
9848 KB |
Output is correct |
8 |
Correct |
10 ms |
9848 KB |
Output is correct |
9 |
Correct |
16 ms |
10132 KB |
Output is correct |
10 |
Correct |
16 ms |
10104 KB |
Output is correct |
11 |
Correct |
16 ms |
10104 KB |
Output is correct |
12 |
Correct |
15 ms |
10104 KB |
Output is correct |
13 |
Correct |
16 ms |
10104 KB |
Output is correct |
14 |
Correct |
16 ms |
10180 KB |
Output is correct |
15 |
Correct |
15 ms |
10104 KB |
Output is correct |
16 |
Correct |
831 ms |
47384 KB |
Output is correct |
17 |
Correct |
2373 ms |
102192 KB |
Output is correct |
18 |
Correct |
138 ms |
18168 KB |
Output is correct |
19 |
Correct |
704 ms |
55240 KB |
Output is correct |
20 |
Correct |
2305 ms |
102032 KB |
Output is correct |
21 |
Correct |
1080 ms |
61388 KB |
Output is correct |
22 |
Correct |
863 ms |
59544 KB |
Output is correct |
23 |
Correct |
2339 ms |
102448 KB |
Output is correct |
24 |
Correct |
2392 ms |
103052 KB |
Output is correct |
25 |
Correct |
2286 ms |
102788 KB |
Output is correct |
26 |
Correct |
737 ms |
54632 KB |
Output is correct |
27 |
Correct |
682 ms |
54456 KB |
Output is correct |
28 |
Correct |
664 ms |
53600 KB |
Output is correct |
29 |
Correct |
682 ms |
54612 KB |
Output is correct |
30 |
Correct |
702 ms |
54376 KB |
Output is correct |
31 |
Correct |
10 ms |
9720 KB |
Output is correct |
32 |
Correct |
11 ms |
9720 KB |
Output is correct |
33 |
Correct |
13 ms |
9764 KB |
Output is correct |
34 |
Correct |
11 ms |
9720 KB |
Output is correct |
35 |
Correct |
11 ms |
9720 KB |
Output is correct |
36 |
Correct |
10 ms |
9720 KB |
Output is correct |
37 |
Correct |
11 ms |
9720 KB |
Output is correct |
38 |
Correct |
11 ms |
9720 KB |
Output is correct |
39 |
Correct |
10 ms |
9720 KB |
Output is correct |
40 |
Correct |
11 ms |
9720 KB |
Output is correct |
41 |
Correct |
837 ms |
60100 KB |
Output is correct |
42 |
Correct |
1897 ms |
99904 KB |
Output is correct |
43 |
Correct |
1958 ms |
99864 KB |
Output is correct |
44 |
Correct |
425 ms |
56004 KB |
Output is correct |
45 |
Correct |
1965 ms |
99928 KB |
Output is correct |
46 |
Correct |
1901 ms |
99860 KB |
Output is correct |
47 |
Correct |
1984 ms |
99964 KB |
Output is correct |
48 |
Correct |
1962 ms |
99872 KB |
Output is correct |
49 |
Correct |
1912 ms |
99996 KB |
Output is correct |
50 |
Correct |
1917 ms |
99872 KB |
Output is correct |
51 |
Correct |
1975 ms |
99860 KB |
Output is correct |
52 |
Correct |
1975 ms |
99940 KB |
Output is correct |
53 |
Correct |
1967 ms |
99868 KB |
Output is correct |
54 |
Correct |
1902 ms |
99900 KB |
Output is correct |
55 |
Correct |
1815 ms |
99860 KB |
Output is correct |
56 |
Correct |
1964 ms |
99856 KB |
Output is correct |
57 |
Correct |
2116 ms |
99868 KB |
Output is correct |
58 |
Correct |
1972 ms |
99828 KB |
Output is correct |
59 |
Correct |
452 ms |
57492 KB |
Output is correct |
60 |
Correct |
1920 ms |
100080 KB |
Output is correct |
61 |
Correct |
1118 ms |
100188 KB |
Output is correct |
62 |
Correct |
366 ms |
54032 KB |
Output is correct |
63 |
Correct |
438 ms |
54364 KB |
Output is correct |
64 |
Correct |
381 ms |
54312 KB |
Output is correct |
65 |
Correct |
351 ms |
54032 KB |
Output is correct |
66 |
Correct |
507 ms |
55460 KB |
Output is correct |
67 |
Correct |
494 ms |
58116 KB |
Output is correct |
68 |
Correct |
375 ms |
55104 KB |
Output is correct |
69 |
Correct |
455 ms |
57324 KB |
Output is correct |
70 |
Correct |
349 ms |
55372 KB |
Output is correct |
71 |
Correct |
466 ms |
57244 KB |
Output is correct |
72 |
Correct |
1311 ms |
61552 KB |
Output is correct |
73 |
Correct |
2390 ms |
102032 KB |
Output is correct |
74 |
Correct |
2533 ms |
101920 KB |
Output is correct |
75 |
Correct |
2455 ms |
103528 KB |
Output is correct |
76 |
Correct |
2276 ms |
103132 KB |
Output is correct |
77 |
Correct |
2234 ms |
103128 KB |
Output is correct |
78 |
Correct |
2388 ms |
103316 KB |
Output is correct |
79 |
Correct |
2334 ms |
103432 KB |
Output is correct |
80 |
Correct |
2338 ms |
102264 KB |
Output is correct |
81 |
Correct |
2388 ms |
103216 KB |
Output is correct |
82 |
Correct |
2341 ms |
101944 KB |
Output is correct |
83 |
Correct |
2417 ms |
102384 KB |
Output is correct |
84 |
Correct |
2344 ms |
102988 KB |
Output is correct |
85 |
Correct |
2273 ms |
103324 KB |
Output is correct |
86 |
Correct |
2430 ms |
105584 KB |
Output is correct |
87 |
Correct |
2334 ms |
103656 KB |
Output is correct |
88 |
Correct |
2439 ms |
103884 KB |
Output is correct |
89 |
Correct |
978 ms |
59192 KB |
Output is correct |
90 |
Correct |
2351 ms |
105240 KB |
Output is correct |
91 |
Correct |
1506 ms |
106196 KB |
Output is correct |
92 |
Correct |
799 ms |
55972 KB |
Output is correct |
93 |
Correct |
992 ms |
57328 KB |
Output is correct |
94 |
Correct |
734 ms |
56352 KB |
Output is correct |
95 |
Correct |
715 ms |
56368 KB |
Output is correct |
96 |
Correct |
936 ms |
57024 KB |
Output is correct |
97 |
Correct |
1079 ms |
59580 KB |
Output is correct |
98 |
Correct |
763 ms |
57072 KB |
Output is correct |
99 |
Correct |
1050 ms |
60164 KB |
Output is correct |
100 |
Correct |
726 ms |
57052 KB |
Output is correct |