#include <bits/stdc++.h>
#define ll int
#define f first
#define s second
#define pb push_back
#define mp make_pair
using namespace std;
ll k,n,m,qq,d[100005],p[100005],c[100005],ans[100005],las,fix[100005];
ll qu[100005],sz[100005];
vector<ll>vec[100005];
vector<pair<ll,ll> >v[100005],q[100005];
set<pair<ll,ll> >st;
ll find(ll x){
if(p[x] == x)return x;
return p[x] = find(p[x]);
}
void join(ll x,ll y){
x = find(x);
y = find(y);
if(x == y)return;
if(sz[x] < sz[y])swap(x , y);
qu[x] += qu[y];
sz[x] += sz[y];
for(int i=0; i<q[y].size(); i++){
if(find(q[y][i].f) == x)
ans[q[y][i].s] = min(ans[q[y][i].s] , las);
q[x].pb(q[y][i]);
}
for(int i=0; i<vec[y].size(); i++){
vec[x].pb(vec[y][i]);
}
p[y] = x;
}
int main(){
ios::sync_with_stdio(false);
cin >> n >> m;
for(int i=1; i<=m; i++){
int x,y,z;
cin >> x >> y >> z;
v[x].pb(mp(y , z));
v[y].pb(mp(x , z));
}
cin >> k;
for(int i=1; i<=n; i++){
d[i] = 1000000000;
}
for(int i=1; i<=k; i++){
cin >> c[i];
st.insert(mp(0LL , c[i]));
d[c[i]] = 0;
}
while(st.size()){
ll x = (*st.begin()).s;
st.erase(st.begin());
for(int i=0; i<v[x].size(); i++){
ll to = v[x][i].f;
if(d[to] > d[x] + v[x][i].s){
if(st.find(mp(d[to] , to)) != st.end())st.erase(st.find(mp(d[to] , to)));
d[to] = d[x] + v[x][i].s;
st.insert(mp(d[to] , to));
}
}
}
cin >> qq;
for(int i=1; i<=qq; i++){
ans[i] = 1000000000;
int x,y;
cin >> x >> y;
q[x].pb(mp(y , i));
q[y].pb(mp(x , i));
}
vector<pair<ll,ll> >g;
for(int i=1; i<=n; i++){
g.pb(mp(d[i] , i));
}
sort(g.begin() , g.end());
reverse(g.begin() , g.end());
for(int i=1; i<=n; i++){
p[i] = i;
qu[i] = (int)q[i].size();
vec[i].pb(i);
sz[i] = 1;
}
for(int i=0; i<g.size(); i++){
las = g[i].f;
fix[g[i].s] = 1;
for(int j=0; j<v[g[i].s].size(); j++){
ll to = v[g[i].s][j].f;
if(fix[to] == 1){
join(g[i].s , to);
}
}
}
for(int i=1; i<=qq; i++)
cout << ans[i] << '\n';
return 0;
}
/*
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 'void join(int, int)':
plan.cpp:24:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<q[y].size(); i++){
~^~~~~~~~~~~~
plan.cpp:29:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<vec[y].size(); i++){
~^~~~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:60:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<v[x].size(); i++){
~^~~~~~~~~~~~
plan.cpp:97:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<g.size(); i++){
~^~~~~~~~~
plan.cpp:100:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0; j<v[g[i].s].size(); j++){
~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
7416 KB |
Output is correct |
2 |
Correct |
9 ms |
7544 KB |
Output is correct |
3 |
Correct |
10 ms |
7544 KB |
Output is correct |
4 |
Correct |
8 ms |
7416 KB |
Output is correct |
5 |
Correct |
9 ms |
7544 KB |
Output is correct |
6 |
Correct |
10 ms |
7572 KB |
Output is correct |
7 |
Correct |
8 ms |
7408 KB |
Output is correct |
8 |
Correct |
8 ms |
7416 KB |
Output is correct |
9 |
Correct |
9 ms |
7592 KB |
Output is correct |
10 |
Correct |
10 ms |
7668 KB |
Output is correct |
11 |
Correct |
10 ms |
7588 KB |
Output is correct |
12 |
Correct |
9 ms |
7544 KB |
Output is correct |
13 |
Correct |
10 ms |
7672 KB |
Output is correct |
14 |
Correct |
10 ms |
7672 KB |
Output is correct |
15 |
Correct |
10 ms |
7672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
7416 KB |
Output is correct |
2 |
Correct |
9 ms |
7544 KB |
Output is correct |
3 |
Correct |
10 ms |
7544 KB |
Output is correct |
4 |
Correct |
8 ms |
7416 KB |
Output is correct |
5 |
Correct |
9 ms |
7544 KB |
Output is correct |
6 |
Correct |
10 ms |
7572 KB |
Output is correct |
7 |
Correct |
8 ms |
7408 KB |
Output is correct |
8 |
Correct |
8 ms |
7416 KB |
Output is correct |
9 |
Correct |
9 ms |
7592 KB |
Output is correct |
10 |
Correct |
10 ms |
7668 KB |
Output is correct |
11 |
Correct |
10 ms |
7588 KB |
Output is correct |
12 |
Correct |
9 ms |
7544 KB |
Output is correct |
13 |
Correct |
10 ms |
7672 KB |
Output is correct |
14 |
Correct |
10 ms |
7672 KB |
Output is correct |
15 |
Correct |
10 ms |
7672 KB |
Output is correct |
16 |
Correct |
271 ms |
24224 KB |
Output is correct |
17 |
Correct |
736 ms |
34284 KB |
Output is correct |
18 |
Correct |
51 ms |
10488 KB |
Output is correct |
19 |
Correct |
228 ms |
24372 KB |
Output is correct |
20 |
Correct |
766 ms |
33724 KB |
Output is correct |
21 |
Correct |
420 ms |
26824 KB |
Output is correct |
22 |
Correct |
220 ms |
23484 KB |
Output is correct |
23 |
Correct |
754 ms |
33040 KB |
Output is correct |
24 |
Correct |
746 ms |
33016 KB |
Output is correct |
25 |
Correct |
754 ms |
33068 KB |
Output is correct |
26 |
Correct |
222 ms |
23772 KB |
Output is correct |
27 |
Correct |
211 ms |
23912 KB |
Output is correct |
28 |
Correct |
222 ms |
23700 KB |
Output is correct |
29 |
Correct |
226 ms |
23936 KB |
Output is correct |
30 |
Correct |
221 ms |
23916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
7416 KB |
Output is correct |
2 |
Correct |
8 ms |
7416 KB |
Output is correct |
3 |
Correct |
8 ms |
7416 KB |
Output is correct |
4 |
Correct |
8 ms |
7416 KB |
Output is correct |
5 |
Correct |
9 ms |
7416 KB |
Output is correct |
6 |
Correct |
8 ms |
7464 KB |
Output is correct |
7 |
Correct |
8 ms |
7416 KB |
Output is correct |
8 |
Correct |
8 ms |
7416 KB |
Output is correct |
9 |
Correct |
8 ms |
7420 KB |
Output is correct |
10 |
Correct |
8 ms |
7416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
308 ms |
20196 KB |
Output is correct |
2 |
Correct |
654 ms |
26748 KB |
Output is correct |
3 |
Correct |
620 ms |
26848 KB |
Output is correct |
4 |
Correct |
118 ms |
17488 KB |
Output is correct |
5 |
Correct |
644 ms |
26804 KB |
Output is correct |
6 |
Correct |
627 ms |
26920 KB |
Output is correct |
7 |
Correct |
687 ms |
26964 KB |
Output is correct |
8 |
Correct |
666 ms |
26732 KB |
Output is correct |
9 |
Correct |
649 ms |
26796 KB |
Output is correct |
10 |
Correct |
622 ms |
26868 KB |
Output is correct |
11 |
Correct |
631 ms |
26848 KB |
Output is correct |
12 |
Correct |
631 ms |
26960 KB |
Output is correct |
13 |
Correct |
646 ms |
26996 KB |
Output is correct |
14 |
Correct |
623 ms |
26896 KB |
Output is correct |
15 |
Correct |
621 ms |
26844 KB |
Output is correct |
16 |
Correct |
639 ms |
26884 KB |
Output is correct |
17 |
Correct |
605 ms |
26812 KB |
Output is correct |
18 |
Correct |
629 ms |
26884 KB |
Output is correct |
19 |
Correct |
119 ms |
17324 KB |
Output is correct |
20 |
Correct |
630 ms |
26812 KB |
Output is correct |
21 |
Correct |
543 ms |
27140 KB |
Output is correct |
22 |
Correct |
155 ms |
18316 KB |
Output is correct |
23 |
Correct |
139 ms |
18792 KB |
Output is correct |
24 |
Correct |
155 ms |
18576 KB |
Output is correct |
25 |
Correct |
155 ms |
18376 KB |
Output is correct |
26 |
Correct |
159 ms |
19404 KB |
Output is correct |
27 |
Correct |
125 ms |
17548 KB |
Output is correct |
28 |
Correct |
162 ms |
18568 KB |
Output is correct |
29 |
Correct |
122 ms |
17388 KB |
Output is correct |
30 |
Correct |
149 ms |
18372 KB |
Output is correct |
31 |
Correct |
120 ms |
17424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
7416 KB |
Output is correct |
2 |
Correct |
9 ms |
7544 KB |
Output is correct |
3 |
Correct |
10 ms |
7544 KB |
Output is correct |
4 |
Correct |
8 ms |
7416 KB |
Output is correct |
5 |
Correct |
9 ms |
7544 KB |
Output is correct |
6 |
Correct |
10 ms |
7572 KB |
Output is correct |
7 |
Correct |
8 ms |
7408 KB |
Output is correct |
8 |
Correct |
8 ms |
7416 KB |
Output is correct |
9 |
Correct |
9 ms |
7592 KB |
Output is correct |
10 |
Correct |
10 ms |
7668 KB |
Output is correct |
11 |
Correct |
10 ms |
7588 KB |
Output is correct |
12 |
Correct |
9 ms |
7544 KB |
Output is correct |
13 |
Correct |
10 ms |
7672 KB |
Output is correct |
14 |
Correct |
10 ms |
7672 KB |
Output is correct |
15 |
Correct |
10 ms |
7672 KB |
Output is correct |
16 |
Correct |
271 ms |
24224 KB |
Output is correct |
17 |
Correct |
736 ms |
34284 KB |
Output is correct |
18 |
Correct |
51 ms |
10488 KB |
Output is correct |
19 |
Correct |
228 ms |
24372 KB |
Output is correct |
20 |
Correct |
766 ms |
33724 KB |
Output is correct |
21 |
Correct |
420 ms |
26824 KB |
Output is correct |
22 |
Correct |
220 ms |
23484 KB |
Output is correct |
23 |
Correct |
754 ms |
33040 KB |
Output is correct |
24 |
Correct |
746 ms |
33016 KB |
Output is correct |
25 |
Correct |
754 ms |
33068 KB |
Output is correct |
26 |
Correct |
222 ms |
23772 KB |
Output is correct |
27 |
Correct |
211 ms |
23912 KB |
Output is correct |
28 |
Correct |
222 ms |
23700 KB |
Output is correct |
29 |
Correct |
226 ms |
23936 KB |
Output is correct |
30 |
Correct |
221 ms |
23916 KB |
Output is correct |
31 |
Correct |
7 ms |
7416 KB |
Output is correct |
32 |
Correct |
8 ms |
7416 KB |
Output is correct |
33 |
Correct |
8 ms |
7416 KB |
Output is correct |
34 |
Correct |
8 ms |
7416 KB |
Output is correct |
35 |
Correct |
9 ms |
7416 KB |
Output is correct |
36 |
Correct |
8 ms |
7464 KB |
Output is correct |
37 |
Correct |
8 ms |
7416 KB |
Output is correct |
38 |
Correct |
8 ms |
7416 KB |
Output is correct |
39 |
Correct |
8 ms |
7420 KB |
Output is correct |
40 |
Correct |
8 ms |
7416 KB |
Output is correct |
41 |
Correct |
308 ms |
20196 KB |
Output is correct |
42 |
Correct |
654 ms |
26748 KB |
Output is correct |
43 |
Correct |
620 ms |
26848 KB |
Output is correct |
44 |
Correct |
118 ms |
17488 KB |
Output is correct |
45 |
Correct |
644 ms |
26804 KB |
Output is correct |
46 |
Correct |
627 ms |
26920 KB |
Output is correct |
47 |
Correct |
687 ms |
26964 KB |
Output is correct |
48 |
Correct |
666 ms |
26732 KB |
Output is correct |
49 |
Correct |
649 ms |
26796 KB |
Output is correct |
50 |
Correct |
622 ms |
26868 KB |
Output is correct |
51 |
Correct |
631 ms |
26848 KB |
Output is correct |
52 |
Correct |
631 ms |
26960 KB |
Output is correct |
53 |
Correct |
646 ms |
26996 KB |
Output is correct |
54 |
Correct |
623 ms |
26896 KB |
Output is correct |
55 |
Correct |
621 ms |
26844 KB |
Output is correct |
56 |
Correct |
639 ms |
26884 KB |
Output is correct |
57 |
Correct |
605 ms |
26812 KB |
Output is correct |
58 |
Correct |
629 ms |
26884 KB |
Output is correct |
59 |
Correct |
119 ms |
17324 KB |
Output is correct |
60 |
Correct |
630 ms |
26812 KB |
Output is correct |
61 |
Correct |
543 ms |
27140 KB |
Output is correct |
62 |
Correct |
155 ms |
18316 KB |
Output is correct |
63 |
Correct |
139 ms |
18792 KB |
Output is correct |
64 |
Correct |
155 ms |
18576 KB |
Output is correct |
65 |
Correct |
155 ms |
18376 KB |
Output is correct |
66 |
Correct |
159 ms |
19404 KB |
Output is correct |
67 |
Correct |
125 ms |
17548 KB |
Output is correct |
68 |
Correct |
162 ms |
18568 KB |
Output is correct |
69 |
Correct |
122 ms |
17388 KB |
Output is correct |
70 |
Correct |
149 ms |
18372 KB |
Output is correct |
71 |
Correct |
120 ms |
17424 KB |
Output is correct |
72 |
Correct |
395 ms |
26860 KB |
Output is correct |
73 |
Correct |
721 ms |
32856 KB |
Output is correct |
74 |
Correct |
732 ms |
33036 KB |
Output is correct |
75 |
Correct |
766 ms |
33032 KB |
Output is correct |
76 |
Correct |
758 ms |
32876 KB |
Output is correct |
77 |
Correct |
708 ms |
32876 KB |
Output is correct |
78 |
Correct |
722 ms |
33112 KB |
Output is correct |
79 |
Correct |
724 ms |
32880 KB |
Output is correct |
80 |
Correct |
768 ms |
33024 KB |
Output is correct |
81 |
Correct |
749 ms |
33072 KB |
Output is correct |
82 |
Correct |
718 ms |
32880 KB |
Output is correct |
83 |
Correct |
733 ms |
33024 KB |
Output is correct |
84 |
Correct |
740 ms |
32988 KB |
Output is correct |
85 |
Correct |
719 ms |
32924 KB |
Output is correct |
86 |
Correct |
695 ms |
33228 KB |
Output is correct |
87 |
Correct |
713 ms |
33000 KB |
Output is correct |
88 |
Correct |
732 ms |
33280 KB |
Output is correct |
89 |
Correct |
199 ms |
23652 KB |
Output is correct |
90 |
Correct |
722 ms |
32956 KB |
Output is correct |
91 |
Correct |
602 ms |
33400 KB |
Output is correct |
92 |
Correct |
224 ms |
24040 KB |
Output is correct |
93 |
Correct |
252 ms |
31332 KB |
Output is correct |
94 |
Correct |
233 ms |
24044 KB |
Output is correct |
95 |
Correct |
242 ms |
24044 KB |
Output is correct |
96 |
Correct |
282 ms |
32880 KB |
Output is correct |
97 |
Correct |
209 ms |
24300 KB |
Output is correct |
98 |
Correct |
248 ms |
24044 KB |
Output is correct |
99 |
Correct |
209 ms |
24212 KB |
Output is correct |
100 |
Correct |
233 ms |
24040 KB |
Output is correct |