#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define REP(i,n) for (int i = 0; i<n; ++i)
#define pii pair<int, int>
#define SZ(x) (int)((x).size())
#define ALL(x) x.begin(), x.end()
#define pb push_back
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y){cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT
const int maxn = 1e5+5;
vector<pii> g[maxn];
ll d[maxn], ans[maxn];
int par[maxn]; bool done[maxn];
int find(int x) {return x == par[x]? x : par[x] = find(par[x]);}
void mrg(int a, int b) {
if (!done[b]) return;
a = find(a); b = find(b); par[a] = b;
// done[b] = 1;
}
bool can(int a, int b) {
return done[a] && done[b] && find(a) == find(b);
}
struct chunk{
int l,r;
vector<pair<int, pii> > v;
};
signed main(){
ios::sync_with_stdio(0), cin.tie(0);
bug(1,2);
int n,m; cin>>n>>m;
REP(i,m) {
int a,b,w; cin>>a>>b>>w; --a; --b;
g[a].pb({b,w});
g[b].pb({a,w});
}
priority_queue<pii, vector<pii>, greater<pii> > pq;
vector<int> dg;
int nbad; cin>>nbad;
memset(d, 0x3f, sizeof d);
REP(i,nbad) {
int x; cin>>x; x--; dg.pb(x);
d[x] = 0;
pq.push({0,x});
}
while (!pq.empty() ) {
int w = pq.top().f, v = pq.top().s; pq.pop();
if (d[v] != w) continue;
for (pii u : g[v]) {
if (d[u.f] > d[v] + u.s) {
d[u.f] = d[v] + u.s;
pq.push({d[u.f], u.f});
}
}
}
vector<pii> here;
chunk gogo; gogo.l=0, gogo.r = n-1;
REP(i,n) {
here.pb({d[i], i});
bug(i, d[i]);
}
int qu; cin>>qu;
REP(i,qu) {
int a,b; cin>>a>>b;
gogo.v.pb({i, {a-1, b-1}});
}
sort(ALL(here)); reverse(ALL(here));
queue<chunk> q;
q.push(gogo);
int now = 10000000;
while (!q.empty()){
chunk c = q.front(); q.pop();
if (c.l == c.r) {
for (auto u : c.v) {
ans[u.f] = here[c.l].f;
}
continue;
}
int mid = ((c.l) + (c.r)) >>1;
if (now > mid) {
now = -1;
REP(i,n) {
par[i] = i; done[i] = 0;
}
}
while (now<mid) {
++now;
int v = here[now].s; done[v] = 1;
for (pii u : g[v]) {
mrg(v, u.f);
}
}
chunk lc, rc; lc.l = c.l, lc.r = mid; rc.l=mid+1, rc.r=c.r;
for (auto u : c.v) {
if (can(u.s.f, u.s.s)) {
lc.v.pb(u);
}else{
rc.v.pb(u);
}
}
if (!lc.v.empty()) q.push(lc);
if (!rc.v.empty()) q.push(rc);
}
REP(i,qu) {
cout<<ans[i]<<endl;
}
}
/*
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
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
3436 KB |
Output is correct |
2 |
Correct |
3 ms |
3564 KB |
Output is correct |
3 |
Correct |
4 ms |
3564 KB |
Output is correct |
4 |
Correct |
2 ms |
3436 KB |
Output is correct |
5 |
Correct |
4 ms |
3564 KB |
Output is correct |
6 |
Correct |
4 ms |
3692 KB |
Output is correct |
7 |
Correct |
3 ms |
3436 KB |
Output is correct |
8 |
Correct |
3 ms |
3436 KB |
Output is correct |
9 |
Correct |
4 ms |
3692 KB |
Output is correct |
10 |
Correct |
4 ms |
3692 KB |
Output is correct |
11 |
Correct |
4 ms |
3692 KB |
Output is correct |
12 |
Correct |
4 ms |
3692 KB |
Output is correct |
13 |
Correct |
4 ms |
3692 KB |
Output is correct |
14 |
Correct |
4 ms |
3692 KB |
Output is correct |
15 |
Correct |
4 ms |
3692 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
3436 KB |
Output is correct |
2 |
Correct |
3 ms |
3564 KB |
Output is correct |
3 |
Correct |
4 ms |
3564 KB |
Output is correct |
4 |
Correct |
2 ms |
3436 KB |
Output is correct |
5 |
Correct |
4 ms |
3564 KB |
Output is correct |
6 |
Correct |
4 ms |
3692 KB |
Output is correct |
7 |
Correct |
3 ms |
3436 KB |
Output is correct |
8 |
Correct |
3 ms |
3436 KB |
Output is correct |
9 |
Correct |
4 ms |
3692 KB |
Output is correct |
10 |
Correct |
4 ms |
3692 KB |
Output is correct |
11 |
Correct |
4 ms |
3692 KB |
Output is correct |
12 |
Correct |
4 ms |
3692 KB |
Output is correct |
13 |
Correct |
4 ms |
3692 KB |
Output is correct |
14 |
Correct |
4 ms |
3692 KB |
Output is correct |
15 |
Correct |
4 ms |
3692 KB |
Output is correct |
16 |
Correct |
436 ms |
14572 KB |
Output is correct |
17 |
Correct |
1178 ms |
25800 KB |
Output is correct |
18 |
Correct |
60 ms |
5716 KB |
Output is correct |
19 |
Correct |
193 ms |
18300 KB |
Output is correct |
20 |
Correct |
1199 ms |
25920 KB |
Output is correct |
21 |
Correct |
656 ms |
17856 KB |
Output is correct |
22 |
Correct |
250 ms |
15408 KB |
Output is correct |
23 |
Correct |
1165 ms |
25844 KB |
Output is correct |
24 |
Correct |
1186 ms |
26052 KB |
Output is correct |
25 |
Correct |
1176 ms |
25272 KB |
Output is correct |
26 |
Correct |
232 ms |
16580 KB |
Output is correct |
27 |
Correct |
195 ms |
19516 KB |
Output is correct |
28 |
Correct |
222 ms |
17492 KB |
Output is correct |
29 |
Correct |
213 ms |
17548 KB |
Output is correct |
30 |
Correct |
189 ms |
18276 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
3436 KB |
Output is correct |
2 |
Correct |
2 ms |
3436 KB |
Output is correct |
3 |
Correct |
3 ms |
3436 KB |
Output is correct |
4 |
Correct |
3 ms |
3436 KB |
Output is correct |
5 |
Correct |
3 ms |
3436 KB |
Output is correct |
6 |
Correct |
3 ms |
3436 KB |
Output is correct |
7 |
Correct |
3 ms |
3436 KB |
Output is correct |
8 |
Correct |
3 ms |
3436 KB |
Output is correct |
9 |
Correct |
3 ms |
3436 KB |
Output is correct |
10 |
Correct |
2 ms |
3436 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
274 ms |
11756 KB |
Output is correct |
2 |
Correct |
612 ms |
20324 KB |
Output is correct |
3 |
Correct |
693 ms |
20196 KB |
Output is correct |
4 |
Correct |
72 ms |
8032 KB |
Output is correct |
5 |
Correct |
533 ms |
20068 KB |
Output is correct |
6 |
Correct |
463 ms |
20072 KB |
Output is correct |
7 |
Correct |
514 ms |
20192 KB |
Output is correct |
8 |
Correct |
525 ms |
20068 KB |
Output is correct |
9 |
Correct |
478 ms |
20068 KB |
Output is correct |
10 |
Correct |
579 ms |
20072 KB |
Output is correct |
11 |
Correct |
680 ms |
20068 KB |
Output is correct |
12 |
Correct |
705 ms |
20072 KB |
Output is correct |
13 |
Correct |
777 ms |
20224 KB |
Output is correct |
14 |
Correct |
536 ms |
20084 KB |
Output is correct |
15 |
Correct |
656 ms |
20956 KB |
Output is correct |
16 |
Correct |
663 ms |
20196 KB |
Output is correct |
17 |
Correct |
506 ms |
20068 KB |
Output is correct |
18 |
Correct |
477 ms |
20052 KB |
Output is correct |
19 |
Correct |
72 ms |
8032 KB |
Output is correct |
20 |
Correct |
696 ms |
20068 KB |
Output is correct |
21 |
Correct |
440 ms |
20316 KB |
Output is correct |
22 |
Correct |
119 ms |
12900 KB |
Output is correct |
23 |
Correct |
157 ms |
8544 KB |
Output is correct |
24 |
Correct |
114 ms |
11264 KB |
Output is correct |
25 |
Correct |
119 ms |
12260 KB |
Output is correct |
26 |
Correct |
133 ms |
8544 KB |
Output is correct |
27 |
Correct |
67 ms |
8160 KB |
Output is correct |
28 |
Correct |
136 ms |
10976 KB |
Output is correct |
29 |
Correct |
74 ms |
8032 KB |
Output is correct |
30 |
Correct |
102 ms |
11100 KB |
Output is correct |
31 |
Correct |
67 ms |
8032 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
3436 KB |
Output is correct |
2 |
Correct |
3 ms |
3564 KB |
Output is correct |
3 |
Correct |
4 ms |
3564 KB |
Output is correct |
4 |
Correct |
2 ms |
3436 KB |
Output is correct |
5 |
Correct |
4 ms |
3564 KB |
Output is correct |
6 |
Correct |
4 ms |
3692 KB |
Output is correct |
7 |
Correct |
3 ms |
3436 KB |
Output is correct |
8 |
Correct |
3 ms |
3436 KB |
Output is correct |
9 |
Correct |
4 ms |
3692 KB |
Output is correct |
10 |
Correct |
4 ms |
3692 KB |
Output is correct |
11 |
Correct |
4 ms |
3692 KB |
Output is correct |
12 |
Correct |
4 ms |
3692 KB |
Output is correct |
13 |
Correct |
4 ms |
3692 KB |
Output is correct |
14 |
Correct |
4 ms |
3692 KB |
Output is correct |
15 |
Correct |
4 ms |
3692 KB |
Output is correct |
16 |
Correct |
436 ms |
14572 KB |
Output is correct |
17 |
Correct |
1178 ms |
25800 KB |
Output is correct |
18 |
Correct |
60 ms |
5716 KB |
Output is correct |
19 |
Correct |
193 ms |
18300 KB |
Output is correct |
20 |
Correct |
1199 ms |
25920 KB |
Output is correct |
21 |
Correct |
656 ms |
17856 KB |
Output is correct |
22 |
Correct |
250 ms |
15408 KB |
Output is correct |
23 |
Correct |
1165 ms |
25844 KB |
Output is correct |
24 |
Correct |
1186 ms |
26052 KB |
Output is correct |
25 |
Correct |
1176 ms |
25272 KB |
Output is correct |
26 |
Correct |
232 ms |
16580 KB |
Output is correct |
27 |
Correct |
195 ms |
19516 KB |
Output is correct |
28 |
Correct |
222 ms |
17492 KB |
Output is correct |
29 |
Correct |
213 ms |
17548 KB |
Output is correct |
30 |
Correct |
189 ms |
18276 KB |
Output is correct |
31 |
Correct |
3 ms |
3436 KB |
Output is correct |
32 |
Correct |
2 ms |
3436 KB |
Output is correct |
33 |
Correct |
3 ms |
3436 KB |
Output is correct |
34 |
Correct |
3 ms |
3436 KB |
Output is correct |
35 |
Correct |
3 ms |
3436 KB |
Output is correct |
36 |
Correct |
3 ms |
3436 KB |
Output is correct |
37 |
Correct |
3 ms |
3436 KB |
Output is correct |
38 |
Correct |
3 ms |
3436 KB |
Output is correct |
39 |
Correct |
3 ms |
3436 KB |
Output is correct |
40 |
Correct |
2 ms |
3436 KB |
Output is correct |
41 |
Correct |
274 ms |
11756 KB |
Output is correct |
42 |
Correct |
612 ms |
20324 KB |
Output is correct |
43 |
Correct |
693 ms |
20196 KB |
Output is correct |
44 |
Correct |
72 ms |
8032 KB |
Output is correct |
45 |
Correct |
533 ms |
20068 KB |
Output is correct |
46 |
Correct |
463 ms |
20072 KB |
Output is correct |
47 |
Correct |
514 ms |
20192 KB |
Output is correct |
48 |
Correct |
525 ms |
20068 KB |
Output is correct |
49 |
Correct |
478 ms |
20068 KB |
Output is correct |
50 |
Correct |
579 ms |
20072 KB |
Output is correct |
51 |
Correct |
680 ms |
20068 KB |
Output is correct |
52 |
Correct |
705 ms |
20072 KB |
Output is correct |
53 |
Correct |
777 ms |
20224 KB |
Output is correct |
54 |
Correct |
536 ms |
20084 KB |
Output is correct |
55 |
Correct |
656 ms |
20956 KB |
Output is correct |
56 |
Correct |
663 ms |
20196 KB |
Output is correct |
57 |
Correct |
506 ms |
20068 KB |
Output is correct |
58 |
Correct |
477 ms |
20052 KB |
Output is correct |
59 |
Correct |
72 ms |
8032 KB |
Output is correct |
60 |
Correct |
696 ms |
20068 KB |
Output is correct |
61 |
Correct |
440 ms |
20316 KB |
Output is correct |
62 |
Correct |
119 ms |
12900 KB |
Output is correct |
63 |
Correct |
157 ms |
8544 KB |
Output is correct |
64 |
Correct |
114 ms |
11264 KB |
Output is correct |
65 |
Correct |
119 ms |
12260 KB |
Output is correct |
66 |
Correct |
133 ms |
8544 KB |
Output is correct |
67 |
Correct |
67 ms |
8160 KB |
Output is correct |
68 |
Correct |
136 ms |
10976 KB |
Output is correct |
69 |
Correct |
74 ms |
8032 KB |
Output is correct |
70 |
Correct |
102 ms |
11100 KB |
Output is correct |
71 |
Correct |
67 ms |
8032 KB |
Output is correct |
72 |
Correct |
782 ms |
17892 KB |
Output is correct |
73 |
Correct |
1179 ms |
25800 KB |
Output is correct |
74 |
Correct |
1225 ms |
25532 KB |
Output is correct |
75 |
Correct |
1229 ms |
25924 KB |
Output is correct |
76 |
Correct |
1211 ms |
25796 KB |
Output is correct |
77 |
Correct |
1188 ms |
26052 KB |
Output is correct |
78 |
Correct |
1213 ms |
25784 KB |
Output is correct |
79 |
Correct |
1216 ms |
25844 KB |
Output is correct |
80 |
Correct |
1198 ms |
26068 KB |
Output is correct |
81 |
Correct |
1235 ms |
25572 KB |
Output is correct |
82 |
Correct |
1233 ms |
25872 KB |
Output is correct |
83 |
Correct |
1256 ms |
25864 KB |
Output is correct |
84 |
Correct |
1226 ms |
25988 KB |
Output is correct |
85 |
Correct |
1229 ms |
25784 KB |
Output is correct |
86 |
Correct |
1230 ms |
25772 KB |
Output is correct |
87 |
Correct |
1239 ms |
25740 KB |
Output is correct |
88 |
Correct |
1200 ms |
25916 KB |
Output is correct |
89 |
Correct |
253 ms |
14656 KB |
Output is correct |
90 |
Correct |
1209 ms |
25540 KB |
Output is correct |
91 |
Correct |
1076 ms |
25524 KB |
Output is correct |
92 |
Correct |
205 ms |
18652 KB |
Output is correct |
93 |
Correct |
342 ms |
15112 KB |
Output is correct |
94 |
Correct |
249 ms |
18964 KB |
Output is correct |
95 |
Correct |
213 ms |
19444 KB |
Output is correct |
96 |
Correct |
363 ms |
15080 KB |
Output is correct |
97 |
Correct |
286 ms |
15332 KB |
Output is correct |
98 |
Correct |
249 ms |
18360 KB |
Output is correct |
99 |
Correct |
298 ms |
15400 KB |
Output is correct |
100 |
Correct |
220 ms |
18916 KB |
Output is correct |