#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
using namespace std;
const int N=1000006, INF=1e8+2021;
int x, y, z, d, e, o, n, m, Q, i, j, k, mid, ans[N], f[N], l[N], r[N], pa[N], sz[N], w;
vector <pair<int, int> > v[N], md;
pair<int, int> dist[N], a[N];
priority_queue<pair<int, int> > q;
int find(int v) {
if (v==pa[v]) return v;
return pa[v]=find(pa[v]);
}
void Union(int a, int b) {
a=find(a);
b=find(b);
if (a!=b){
if (sz[a]<sz[b]) swap(a, b);
pa[b]=a;
sz[a]+=sz[b];
}
}
int main(){ios_base::sync_with_stdio(false);
cin>>n>>m;
for (int i=1; i<=n; i++)
dist[i]={INF, i};
for (int i=1; i<=m; i++)
cin>>x>>y>>z,
v[x].pb({y, z}),
v[y].pb({x, z});
cin>>k;
for (int i=1; i<=k; i++)
cin>>x,
q.push({0, x}),
dist[x].F=0;
cin>>Q;
for (int i=1; i<=Q; i++)
cin>>a[i].F>>a[i].S;
while(!q.empty()){
x=q.top().S;
d=-q.top().F;
q.pop();
if(d!=dist[x].F)continue;
for (int i=0; i<v[x].size(); i++) {
y=v[x][i].F;
z=v[x][i].S;
if (dist[x].F+z<dist[y].F) {
dist[y].F=dist[x].F+z;
q.push({-dist[y].F, y});
}
}
}
sort(dist+1, dist+n+1);
for(int i=1; i<=Q; i++)
l[i]=0, r[i]=INF;
for (int i=1; i<=Q; i++)ans[i]=0;
for (int u=1; u<=28; u++){
md.clear();
for (int i=1; i<=Q; i++)
md.pb({l[i]+r[i]>>1, i});
sort(md.begin(), md.end());
for (int i=1; i<=n; i++)
pa[i]=i, sz[i]=1, f[i]=0;
o=n;
for (int i=Q-1; i>=0; i--){
mid=md[i].F;
x=md[i].S;
while(o&&dist[o].F>=mid){
f[dist[o].S]=1;
for (int j=0; j<v[dist[o].S].size(); j++)
if(f[v[dist[o].S][j].F])
Union(dist[o].S, v[dist[o].S][j].F);
o--;
}
if(find(a[x].F)==find(a[x].S)) ans[x]=mid, l[x]=mid+1;
else r[x]=mid-1;
}
}
for (int i=1; i<=Q; i++)
cout<<ans[i]<<'\n';
}
/*
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 'int main()':
plan.cpp:55:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for (int i=0; i<v[x].size(); i++) {
| ~^~~~~~~~~~~~
plan.cpp:75:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
75 | md.pb({l[i]+r[i]>>1, i});
| ~~~~^~~~~
plan.cpp:89:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for (int j=0; j<v[dist[o].S].size(); j++)
| ~^~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
23916 KB |
Output is correct |
2 |
Correct |
19 ms |
24044 KB |
Output is correct |
3 |
Correct |
19 ms |
24044 KB |
Output is correct |
4 |
Correct |
17 ms |
23916 KB |
Output is correct |
5 |
Correct |
18 ms |
24044 KB |
Output is correct |
6 |
Correct |
20 ms |
24172 KB |
Output is correct |
7 |
Correct |
17 ms |
23916 KB |
Output is correct |
8 |
Correct |
16 ms |
23916 KB |
Output is correct |
9 |
Correct |
20 ms |
24044 KB |
Output is correct |
10 |
Correct |
21 ms |
23916 KB |
Output is correct |
11 |
Correct |
23 ms |
24044 KB |
Output is correct |
12 |
Correct |
18 ms |
24044 KB |
Output is correct |
13 |
Correct |
20 ms |
23916 KB |
Output is correct |
14 |
Correct |
20 ms |
24024 KB |
Output is correct |
15 |
Correct |
20 ms |
24044 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
23916 KB |
Output is correct |
2 |
Correct |
19 ms |
24044 KB |
Output is correct |
3 |
Correct |
19 ms |
24044 KB |
Output is correct |
4 |
Correct |
17 ms |
23916 KB |
Output is correct |
5 |
Correct |
18 ms |
24044 KB |
Output is correct |
6 |
Correct |
20 ms |
24172 KB |
Output is correct |
7 |
Correct |
17 ms |
23916 KB |
Output is correct |
8 |
Correct |
16 ms |
23916 KB |
Output is correct |
9 |
Correct |
20 ms |
24044 KB |
Output is correct |
10 |
Correct |
21 ms |
23916 KB |
Output is correct |
11 |
Correct |
23 ms |
24044 KB |
Output is correct |
12 |
Correct |
18 ms |
24044 KB |
Output is correct |
13 |
Correct |
20 ms |
23916 KB |
Output is correct |
14 |
Correct |
20 ms |
24024 KB |
Output is correct |
15 |
Correct |
20 ms |
24044 KB |
Output is correct |
16 |
Correct |
696 ms |
32492 KB |
Output is correct |
17 |
Correct |
1227 ms |
53740 KB |
Output is correct |
18 |
Correct |
87 ms |
26604 KB |
Output is correct |
19 |
Correct |
366 ms |
36840 KB |
Output is correct |
20 |
Correct |
1246 ms |
53572 KB |
Output is correct |
21 |
Correct |
573 ms |
40800 KB |
Output is correct |
22 |
Correct |
775 ms |
35808 KB |
Output is correct |
23 |
Correct |
1214 ms |
53476 KB |
Output is correct |
24 |
Correct |
1192 ms |
53484 KB |
Output is correct |
25 |
Correct |
1070 ms |
53604 KB |
Output is correct |
26 |
Correct |
356 ms |
36584 KB |
Output is correct |
27 |
Correct |
359 ms |
36724 KB |
Output is correct |
28 |
Correct |
366 ms |
36712 KB |
Output is correct |
29 |
Correct |
360 ms |
36712 KB |
Output is correct |
30 |
Correct |
364 ms |
36840 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
23916 KB |
Output is correct |
2 |
Correct |
16 ms |
23916 KB |
Output is correct |
3 |
Correct |
16 ms |
23916 KB |
Output is correct |
4 |
Correct |
16 ms |
23916 KB |
Output is correct |
5 |
Correct |
16 ms |
23916 KB |
Output is correct |
6 |
Correct |
16 ms |
23916 KB |
Output is correct |
7 |
Correct |
16 ms |
23916 KB |
Output is correct |
8 |
Correct |
17 ms |
23916 KB |
Output is correct |
9 |
Correct |
16 ms |
23924 KB |
Output is correct |
10 |
Correct |
17 ms |
23916 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
359 ms |
32976 KB |
Output is correct |
2 |
Correct |
724 ms |
49124 KB |
Output is correct |
3 |
Correct |
746 ms |
49124 KB |
Output is correct |
4 |
Correct |
266 ms |
30572 KB |
Output is correct |
5 |
Correct |
876 ms |
49124 KB |
Output is correct |
6 |
Correct |
553 ms |
49140 KB |
Output is correct |
7 |
Correct |
659 ms |
49120 KB |
Output is correct |
8 |
Correct |
541 ms |
49252 KB |
Output is correct |
9 |
Correct |
574 ms |
49144 KB |
Output is correct |
10 |
Correct |
786 ms |
49128 KB |
Output is correct |
11 |
Correct |
890 ms |
49124 KB |
Output is correct |
12 |
Correct |
756 ms |
49124 KB |
Output is correct |
13 |
Correct |
801 ms |
49124 KB |
Output is correct |
14 |
Correct |
593 ms |
49256 KB |
Output is correct |
15 |
Correct |
758 ms |
49248 KB |
Output is correct |
16 |
Correct |
765 ms |
49252 KB |
Output is correct |
17 |
Correct |
623 ms |
49124 KB |
Output is correct |
18 |
Correct |
607 ms |
49184 KB |
Output is correct |
19 |
Correct |
92 ms |
30572 KB |
Output is correct |
20 |
Correct |
718 ms |
49124 KB |
Output is correct |
21 |
Correct |
535 ms |
49252 KB |
Output is correct |
22 |
Correct |
173 ms |
32484 KB |
Output is correct |
23 |
Correct |
289 ms |
31084 KB |
Output is correct |
24 |
Correct |
166 ms |
32356 KB |
Output is correct |
25 |
Correct |
171 ms |
32312 KB |
Output is correct |
26 |
Correct |
290 ms |
31340 KB |
Output is correct |
27 |
Correct |
276 ms |
30572 KB |
Output is correct |
28 |
Correct |
164 ms |
32356 KB |
Output is correct |
29 |
Correct |
270 ms |
30572 KB |
Output is correct |
30 |
Correct |
161 ms |
32356 KB |
Output is correct |
31 |
Correct |
283 ms |
30700 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
23916 KB |
Output is correct |
2 |
Correct |
19 ms |
24044 KB |
Output is correct |
3 |
Correct |
19 ms |
24044 KB |
Output is correct |
4 |
Correct |
17 ms |
23916 KB |
Output is correct |
5 |
Correct |
18 ms |
24044 KB |
Output is correct |
6 |
Correct |
20 ms |
24172 KB |
Output is correct |
7 |
Correct |
17 ms |
23916 KB |
Output is correct |
8 |
Correct |
16 ms |
23916 KB |
Output is correct |
9 |
Correct |
20 ms |
24044 KB |
Output is correct |
10 |
Correct |
21 ms |
23916 KB |
Output is correct |
11 |
Correct |
23 ms |
24044 KB |
Output is correct |
12 |
Correct |
18 ms |
24044 KB |
Output is correct |
13 |
Correct |
20 ms |
23916 KB |
Output is correct |
14 |
Correct |
20 ms |
24024 KB |
Output is correct |
15 |
Correct |
20 ms |
24044 KB |
Output is correct |
16 |
Correct |
696 ms |
32492 KB |
Output is correct |
17 |
Correct |
1227 ms |
53740 KB |
Output is correct |
18 |
Correct |
87 ms |
26604 KB |
Output is correct |
19 |
Correct |
366 ms |
36840 KB |
Output is correct |
20 |
Correct |
1246 ms |
53572 KB |
Output is correct |
21 |
Correct |
573 ms |
40800 KB |
Output is correct |
22 |
Correct |
775 ms |
35808 KB |
Output is correct |
23 |
Correct |
1214 ms |
53476 KB |
Output is correct |
24 |
Correct |
1192 ms |
53484 KB |
Output is correct |
25 |
Correct |
1070 ms |
53604 KB |
Output is correct |
26 |
Correct |
356 ms |
36584 KB |
Output is correct |
27 |
Correct |
359 ms |
36724 KB |
Output is correct |
28 |
Correct |
366 ms |
36712 KB |
Output is correct |
29 |
Correct |
360 ms |
36712 KB |
Output is correct |
30 |
Correct |
364 ms |
36840 KB |
Output is correct |
31 |
Correct |
16 ms |
23916 KB |
Output is correct |
32 |
Correct |
16 ms |
23916 KB |
Output is correct |
33 |
Correct |
16 ms |
23916 KB |
Output is correct |
34 |
Correct |
16 ms |
23916 KB |
Output is correct |
35 |
Correct |
16 ms |
23916 KB |
Output is correct |
36 |
Correct |
16 ms |
23916 KB |
Output is correct |
37 |
Correct |
16 ms |
23916 KB |
Output is correct |
38 |
Correct |
17 ms |
23916 KB |
Output is correct |
39 |
Correct |
16 ms |
23924 KB |
Output is correct |
40 |
Correct |
17 ms |
23916 KB |
Output is correct |
41 |
Correct |
359 ms |
32976 KB |
Output is correct |
42 |
Correct |
724 ms |
49124 KB |
Output is correct |
43 |
Correct |
746 ms |
49124 KB |
Output is correct |
44 |
Correct |
266 ms |
30572 KB |
Output is correct |
45 |
Correct |
876 ms |
49124 KB |
Output is correct |
46 |
Correct |
553 ms |
49140 KB |
Output is correct |
47 |
Correct |
659 ms |
49120 KB |
Output is correct |
48 |
Correct |
541 ms |
49252 KB |
Output is correct |
49 |
Correct |
574 ms |
49144 KB |
Output is correct |
50 |
Correct |
786 ms |
49128 KB |
Output is correct |
51 |
Correct |
890 ms |
49124 KB |
Output is correct |
52 |
Correct |
756 ms |
49124 KB |
Output is correct |
53 |
Correct |
801 ms |
49124 KB |
Output is correct |
54 |
Correct |
593 ms |
49256 KB |
Output is correct |
55 |
Correct |
758 ms |
49248 KB |
Output is correct |
56 |
Correct |
765 ms |
49252 KB |
Output is correct |
57 |
Correct |
623 ms |
49124 KB |
Output is correct |
58 |
Correct |
607 ms |
49184 KB |
Output is correct |
59 |
Correct |
92 ms |
30572 KB |
Output is correct |
60 |
Correct |
718 ms |
49124 KB |
Output is correct |
61 |
Correct |
535 ms |
49252 KB |
Output is correct |
62 |
Correct |
173 ms |
32484 KB |
Output is correct |
63 |
Correct |
289 ms |
31084 KB |
Output is correct |
64 |
Correct |
166 ms |
32356 KB |
Output is correct |
65 |
Correct |
171 ms |
32312 KB |
Output is correct |
66 |
Correct |
290 ms |
31340 KB |
Output is correct |
67 |
Correct |
276 ms |
30572 KB |
Output is correct |
68 |
Correct |
164 ms |
32356 KB |
Output is correct |
69 |
Correct |
270 ms |
30572 KB |
Output is correct |
70 |
Correct |
161 ms |
32356 KB |
Output is correct |
71 |
Correct |
283 ms |
30700 KB |
Output is correct |
72 |
Correct |
864 ms |
40804 KB |
Output is correct |
73 |
Correct |
1211 ms |
53604 KB |
Output is correct |
74 |
Correct |
1228 ms |
53584 KB |
Output is correct |
75 |
Correct |
1200 ms |
53604 KB |
Output is correct |
76 |
Correct |
1192 ms |
53484 KB |
Output is correct |
77 |
Correct |
1178 ms |
53604 KB |
Output is correct |
78 |
Correct |
1191 ms |
53476 KB |
Output is correct |
79 |
Correct |
1215 ms |
53476 KB |
Output is correct |
80 |
Correct |
1228 ms |
53600 KB |
Output is correct |
81 |
Correct |
1214 ms |
53564 KB |
Output is correct |
82 |
Correct |
1177 ms |
53612 KB |
Output is correct |
83 |
Correct |
1159 ms |
53604 KB |
Output is correct |
84 |
Correct |
1118 ms |
53588 KB |
Output is correct |
85 |
Correct |
1058 ms |
54632 KB |
Output is correct |
86 |
Correct |
1147 ms |
53604 KB |
Output is correct |
87 |
Correct |
1171 ms |
53612 KB |
Output is correct |
88 |
Correct |
1206 ms |
53752 KB |
Output is correct |
89 |
Correct |
815 ms |
35712 KB |
Output is correct |
90 |
Correct |
1197 ms |
53524 KB |
Output is correct |
91 |
Correct |
737 ms |
53468 KB |
Output is correct |
92 |
Correct |
354 ms |
36712 KB |
Output is correct |
93 |
Correct |
773 ms |
35936 KB |
Output is correct |
94 |
Correct |
353 ms |
36584 KB |
Output is correct |
95 |
Correct |
351 ms |
36584 KB |
Output is correct |
96 |
Correct |
621 ms |
35680 KB |
Output is correct |
97 |
Correct |
770 ms |
35296 KB |
Output is correct |
98 |
Correct |
351 ms |
36584 KB |
Output is correct |
99 |
Correct |
737 ms |
35296 KB |
Output is correct |
100 |
Correct |
356 ms |
36584 KB |
Output is correct |