# include <bits/stdc++.h>
# define speed ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
// # define int long long
# define fi first
# define se second
using namespace std;
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
// const int INF = 1e18;
vector < pair < int, int > > adj[N];
int d[N], used[N], sz[N], pr[N], ans[N];
set < int > qr[N];
int find_set( int a ) {
if ( pr[a] == a ) {
return a;
}
return pr[a] = find_set(pr[a]);
}
void merge( int a, int b, int val ) {
a = find_set(a);
b = find_set(b);
if ( a == b ) {
return;
}
if ( sz[a] < sz[b] ) {
swap( a, b );
}
// cout << a << ' ' << b << ' ' << val << endl;
for ( auto i: qr[b] ) {
if ( qr[a].find(i) != qr[a].end() ) {
// cout << i << endl;
ans[i] = val;
qr[a].erase(i);
}
else {
qr[a].insert(i);
}
}
qr[b].clear();
sz[a] += sz[b];
pr[b] = a;
}
int32_t main() {
speed;
int n, m;
cin >> n >> m;
for ( int i = 1; i <= m; i++ ) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
int k;
cin >> k;
set < pair < int, int > > st;
for ( int i = 1; i <= n; i++ ) {
d[i] = mod;
pr[i] = i;
sz[i] = 1;
}
for ( int i = 1; i <= k; i++ ) {
int x;
cin >> x;
d[x] = 0;
st.insert({0, x});
}
while ( !st.empty() ) {
int v = st.begin()->se;
st.erase( { d[v], v } );
// cout << v << " " << d[v] << endl;
for ( auto pr: adj[v] ) {
int u = pr.fi, w = pr.se;
if ( d[v] + w < d[u] ) {
st.erase( { d[u], u } );
d[u] = d[v] + w;
st.insert( { d[u], u } );
}
}
}
int q;
cin >> q;
for ( int i = 1; i <= q; i++ ) {
int u, v;
cin >> u >> v;
qr[u].insert(i);
qr[v].insert(i);
}
vector < pair < int, int > > vc;
for ( int i = 1; i <= n; i++ ) {
vc.push_back( { d[i], i } );
}
sort( vc.rbegin(), vc.rend() );
for ( int i = 0; i < n; i++ ) {
int v = vc[i].se;
used[v] = 1;
// cout << "-> " << v << ' ' << d[v] << endl;
for ( auto pr: adj[v] ) {
int u = pr.fi;
if ( used[u] ) {
// cout << v << ' ' << u << endl;
merge(v, u, d[v]);
}
}
}
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
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7360 KB |
Output is correct |
2 |
Correct |
7 ms |
7504 KB |
Output is correct |
3 |
Correct |
5 ms |
7560 KB |
Output is correct |
4 |
Correct |
3 ms |
7372 KB |
Output is correct |
5 |
Correct |
5 ms |
7548 KB |
Output is correct |
6 |
Correct |
5 ms |
7504 KB |
Output is correct |
7 |
Correct |
4 ms |
7372 KB |
Output is correct |
8 |
Correct |
4 ms |
7372 KB |
Output is correct |
9 |
Correct |
5 ms |
7500 KB |
Output is correct |
10 |
Correct |
5 ms |
7504 KB |
Output is correct |
11 |
Correct |
5 ms |
7500 KB |
Output is correct |
12 |
Correct |
5 ms |
7508 KB |
Output is correct |
13 |
Correct |
5 ms |
7500 KB |
Output is correct |
14 |
Correct |
4 ms |
7500 KB |
Output is correct |
15 |
Correct |
5 ms |
7500 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7360 KB |
Output is correct |
2 |
Correct |
7 ms |
7504 KB |
Output is correct |
3 |
Correct |
5 ms |
7560 KB |
Output is correct |
4 |
Correct |
3 ms |
7372 KB |
Output is correct |
5 |
Correct |
5 ms |
7548 KB |
Output is correct |
6 |
Correct |
5 ms |
7504 KB |
Output is correct |
7 |
Correct |
4 ms |
7372 KB |
Output is correct |
8 |
Correct |
4 ms |
7372 KB |
Output is correct |
9 |
Correct |
5 ms |
7500 KB |
Output is correct |
10 |
Correct |
5 ms |
7504 KB |
Output is correct |
11 |
Correct |
5 ms |
7500 KB |
Output is correct |
12 |
Correct |
5 ms |
7508 KB |
Output is correct |
13 |
Correct |
5 ms |
7500 KB |
Output is correct |
14 |
Correct |
4 ms |
7500 KB |
Output is correct |
15 |
Correct |
5 ms |
7500 KB |
Output is correct |
16 |
Correct |
236 ms |
25856 KB |
Output is correct |
17 |
Correct |
630 ms |
42268 KB |
Output is correct |
18 |
Correct |
39 ms |
10564 KB |
Output is correct |
19 |
Correct |
242 ms |
26820 KB |
Output is correct |
20 |
Correct |
713 ms |
42320 KB |
Output is correct |
21 |
Correct |
386 ms |
30840 KB |
Output is correct |
22 |
Correct |
145 ms |
26416 KB |
Output is correct |
23 |
Correct |
700 ms |
42188 KB |
Output is correct |
24 |
Correct |
616 ms |
42196 KB |
Output is correct |
25 |
Correct |
628 ms |
42172 KB |
Output is correct |
26 |
Correct |
215 ms |
26520 KB |
Output is correct |
27 |
Correct |
233 ms |
26676 KB |
Output is correct |
28 |
Correct |
224 ms |
26616 KB |
Output is correct |
29 |
Correct |
234 ms |
26680 KB |
Output is correct |
30 |
Correct |
223 ms |
26820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7364 KB |
Output is correct |
2 |
Correct |
5 ms |
7364 KB |
Output is correct |
3 |
Correct |
4 ms |
7380 KB |
Output is correct |
4 |
Correct |
5 ms |
7284 KB |
Output is correct |
5 |
Correct |
4 ms |
7368 KB |
Output is correct |
6 |
Correct |
5 ms |
7372 KB |
Output is correct |
7 |
Correct |
4 ms |
7372 KB |
Output is correct |
8 |
Correct |
4 ms |
7372 KB |
Output is correct |
9 |
Correct |
4 ms |
7372 KB |
Output is correct |
10 |
Correct |
4 ms |
7372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
206 ms |
21100 KB |
Output is correct |
2 |
Correct |
431 ms |
31304 KB |
Output is correct |
3 |
Correct |
494 ms |
31376 KB |
Output is correct |
4 |
Correct |
67 ms |
14568 KB |
Output is correct |
5 |
Correct |
460 ms |
31468 KB |
Output is correct |
6 |
Correct |
460 ms |
31424 KB |
Output is correct |
7 |
Correct |
426 ms |
31348 KB |
Output is correct |
8 |
Correct |
449 ms |
31312 KB |
Output is correct |
9 |
Correct |
448 ms |
31236 KB |
Output is correct |
10 |
Correct |
496 ms |
31336 KB |
Output is correct |
11 |
Correct |
453 ms |
31224 KB |
Output is correct |
12 |
Correct |
486 ms |
31336 KB |
Output is correct |
13 |
Correct |
431 ms |
31208 KB |
Output is correct |
14 |
Correct |
427 ms |
31364 KB |
Output is correct |
15 |
Correct |
434 ms |
31304 KB |
Output is correct |
16 |
Correct |
456 ms |
31352 KB |
Output is correct |
17 |
Correct |
420 ms |
31340 KB |
Output is correct |
18 |
Correct |
450 ms |
31272 KB |
Output is correct |
19 |
Correct |
64 ms |
14528 KB |
Output is correct |
20 |
Correct |
485 ms |
31352 KB |
Output is correct |
21 |
Correct |
350 ms |
31060 KB |
Output is correct |
22 |
Correct |
106 ms |
19068 KB |
Output is correct |
23 |
Correct |
90 ms |
15104 KB |
Output is correct |
24 |
Correct |
114 ms |
19124 KB |
Output is correct |
25 |
Correct |
107 ms |
19128 KB |
Output is correct |
26 |
Correct |
97 ms |
15284 KB |
Output is correct |
27 |
Correct |
73 ms |
14504 KB |
Output is correct |
28 |
Correct |
143 ms |
19072 KB |
Output is correct |
29 |
Correct |
70 ms |
14516 KB |
Output is correct |
30 |
Correct |
104 ms |
19132 KB |
Output is correct |
31 |
Correct |
69 ms |
14548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7360 KB |
Output is correct |
2 |
Correct |
7 ms |
7504 KB |
Output is correct |
3 |
Correct |
5 ms |
7560 KB |
Output is correct |
4 |
Correct |
3 ms |
7372 KB |
Output is correct |
5 |
Correct |
5 ms |
7548 KB |
Output is correct |
6 |
Correct |
5 ms |
7504 KB |
Output is correct |
7 |
Correct |
4 ms |
7372 KB |
Output is correct |
8 |
Correct |
4 ms |
7372 KB |
Output is correct |
9 |
Correct |
5 ms |
7500 KB |
Output is correct |
10 |
Correct |
5 ms |
7504 KB |
Output is correct |
11 |
Correct |
5 ms |
7500 KB |
Output is correct |
12 |
Correct |
5 ms |
7508 KB |
Output is correct |
13 |
Correct |
5 ms |
7500 KB |
Output is correct |
14 |
Correct |
4 ms |
7500 KB |
Output is correct |
15 |
Correct |
5 ms |
7500 KB |
Output is correct |
16 |
Correct |
236 ms |
25856 KB |
Output is correct |
17 |
Correct |
630 ms |
42268 KB |
Output is correct |
18 |
Correct |
39 ms |
10564 KB |
Output is correct |
19 |
Correct |
242 ms |
26820 KB |
Output is correct |
20 |
Correct |
713 ms |
42320 KB |
Output is correct |
21 |
Correct |
386 ms |
30840 KB |
Output is correct |
22 |
Correct |
145 ms |
26416 KB |
Output is correct |
23 |
Correct |
700 ms |
42188 KB |
Output is correct |
24 |
Correct |
616 ms |
42196 KB |
Output is correct |
25 |
Correct |
628 ms |
42172 KB |
Output is correct |
26 |
Correct |
215 ms |
26520 KB |
Output is correct |
27 |
Correct |
233 ms |
26676 KB |
Output is correct |
28 |
Correct |
224 ms |
26616 KB |
Output is correct |
29 |
Correct |
234 ms |
26680 KB |
Output is correct |
30 |
Correct |
223 ms |
26820 KB |
Output is correct |
31 |
Correct |
4 ms |
7364 KB |
Output is correct |
32 |
Correct |
5 ms |
7364 KB |
Output is correct |
33 |
Correct |
4 ms |
7380 KB |
Output is correct |
34 |
Correct |
5 ms |
7284 KB |
Output is correct |
35 |
Correct |
4 ms |
7368 KB |
Output is correct |
36 |
Correct |
5 ms |
7372 KB |
Output is correct |
37 |
Correct |
4 ms |
7372 KB |
Output is correct |
38 |
Correct |
4 ms |
7372 KB |
Output is correct |
39 |
Correct |
4 ms |
7372 KB |
Output is correct |
40 |
Correct |
4 ms |
7372 KB |
Output is correct |
41 |
Correct |
206 ms |
21100 KB |
Output is correct |
42 |
Correct |
431 ms |
31304 KB |
Output is correct |
43 |
Correct |
494 ms |
31376 KB |
Output is correct |
44 |
Correct |
67 ms |
14568 KB |
Output is correct |
45 |
Correct |
460 ms |
31468 KB |
Output is correct |
46 |
Correct |
460 ms |
31424 KB |
Output is correct |
47 |
Correct |
426 ms |
31348 KB |
Output is correct |
48 |
Correct |
449 ms |
31312 KB |
Output is correct |
49 |
Correct |
448 ms |
31236 KB |
Output is correct |
50 |
Correct |
496 ms |
31336 KB |
Output is correct |
51 |
Correct |
453 ms |
31224 KB |
Output is correct |
52 |
Correct |
486 ms |
31336 KB |
Output is correct |
53 |
Correct |
431 ms |
31208 KB |
Output is correct |
54 |
Correct |
427 ms |
31364 KB |
Output is correct |
55 |
Correct |
434 ms |
31304 KB |
Output is correct |
56 |
Correct |
456 ms |
31352 KB |
Output is correct |
57 |
Correct |
420 ms |
31340 KB |
Output is correct |
58 |
Correct |
450 ms |
31272 KB |
Output is correct |
59 |
Correct |
64 ms |
14528 KB |
Output is correct |
60 |
Correct |
485 ms |
31352 KB |
Output is correct |
61 |
Correct |
350 ms |
31060 KB |
Output is correct |
62 |
Correct |
106 ms |
19068 KB |
Output is correct |
63 |
Correct |
90 ms |
15104 KB |
Output is correct |
64 |
Correct |
114 ms |
19124 KB |
Output is correct |
65 |
Correct |
107 ms |
19128 KB |
Output is correct |
66 |
Correct |
97 ms |
15284 KB |
Output is correct |
67 |
Correct |
73 ms |
14504 KB |
Output is correct |
68 |
Correct |
143 ms |
19072 KB |
Output is correct |
69 |
Correct |
70 ms |
14516 KB |
Output is correct |
70 |
Correct |
104 ms |
19132 KB |
Output is correct |
71 |
Correct |
69 ms |
14548 KB |
Output is correct |
72 |
Correct |
404 ms |
30776 KB |
Output is correct |
73 |
Correct |
632 ms |
42288 KB |
Output is correct |
74 |
Correct |
673 ms |
42220 KB |
Output is correct |
75 |
Correct |
625 ms |
42296 KB |
Output is correct |
76 |
Correct |
641 ms |
42320 KB |
Output is correct |
77 |
Correct |
644 ms |
42168 KB |
Output is correct |
78 |
Correct |
620 ms |
42252 KB |
Output is correct |
79 |
Correct |
598 ms |
42172 KB |
Output is correct |
80 |
Correct |
610 ms |
42420 KB |
Output is correct |
81 |
Correct |
608 ms |
42152 KB |
Output is correct |
82 |
Correct |
617 ms |
42280 KB |
Output is correct |
83 |
Correct |
584 ms |
42392 KB |
Output is correct |
84 |
Correct |
593 ms |
42136 KB |
Output is correct |
85 |
Correct |
606 ms |
42204 KB |
Output is correct |
86 |
Correct |
623 ms |
42260 KB |
Output is correct |
87 |
Correct |
628 ms |
42296 KB |
Output is correct |
88 |
Correct |
612 ms |
42144 KB |
Output is correct |
89 |
Correct |
243 ms |
26460 KB |
Output is correct |
90 |
Correct |
649 ms |
42196 KB |
Output is correct |
91 |
Correct |
571 ms |
42436 KB |
Output is correct |
92 |
Correct |
282 ms |
26608 KB |
Output is correct |
93 |
Correct |
344 ms |
26976 KB |
Output is correct |
94 |
Correct |
280 ms |
26560 KB |
Output is correct |
95 |
Correct |
282 ms |
26624 KB |
Output is correct |
96 |
Correct |
414 ms |
26304 KB |
Output is correct |
97 |
Correct |
278 ms |
26164 KB |
Output is correct |
98 |
Correct |
269 ms |
26552 KB |
Output is correct |
99 |
Correct |
277 ms |
26152 KB |
Output is correct |
100 |
Correct |
278 ms |
26680 KB |
Output is correct |