# include <stdio.h>
# include <bits/stdc++.h>
#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define For(i,x,y) for (ll i = x; i <= y; i ++)
#define FOr(i,x,y) for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0)
// ROAD to... Red
using namespace std;
inline bool isvowel (char c) {
c = tolower(c);
if (c == 'a' || c == 'e' || c == 'i' || c == 'y' || c == 'o' || c == 'u') return 1;
return 0;
}
const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 1e9 + 11;
const int mxn = 1e6 + 9;
const int N = 6e5 + 123;
const int M = 22;
const int pri = 997;
const int Magic = 2101;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
int n, m, k;
bool u[N];
int tin[N], tout[N], timer;
vector < pair < int, int > > g[N], gr[N];
vector < pair < int, pair < int, int > > > all;
int d[N], mx[N][22], pr[N][22];
int p[N], sz[N];
int get (int a) {
if (a == p[a]) return a;
return p[a] = get(p[a]);
}
bool uni (int a, int b) {
a = get(a), b = get(b);
if (a == b) return 0;
if (sz[a] > sz[b]) swap(a, b);
sz[b] += sz[a];
p[a] = b;
return 1;
}
void dfs (int v) {
u[v] = 1;
tin[v] = ++ timer;
For (i, 1, 18) {
pr[v][i] = pr[pr[v][i - 1]][i - 1];
mx[v][i] = min(mx[v][i - 1], mx[pr[v][i - 1]][i - 1]);
}
for (auto to : gr[v]) {
if (!u[to.F]) {
mx[to.F][0] = to.S;
pr[to.F][0] = v;
dfs (to.F);
}
}
tout[v] = timer;
}
bool upper (int a, int b) {
return tin[a] <= tin[b] && tout[b] <= tout[a];
}
int lca (int a, int b) {
if (upper(a, b)) return a;
if (upper(b, a)) return b;
for (int i = 18; i >= 0; i --) {
if (!upper(pr[a][i], b))
a = pr[a][i];
}
return pr[a][0];
}
int get (int a, int b) {
int res = inf;
if (a == b) return res;
for (int i = 18; i >= 0; i --) {
if (!upper(pr[a][i], b)) {
res = min(res, mx[a][i]);
a = pr[a][i];
}
}
return min(res, mx[a][0]);
}
int main () {
SpeedForce;
// freopen("out", "w", stdout);
cin >> n >> m;
tout[0] = inf;
For (i, 1, m) {
int l, r, x;
cin >> l >> r >> x;
g[l].pb(mp(r, x));
g[r].pb(mp(l, x));
all.pb(mp(x, mp(l, r)));
}
set < pair < int, int > > s;
cin >> k;
for (int i = 1; i <= n; i ++) {
d[i] = inf;
p[i] = i;
sz[i] = 1;
}
for (int i = 1; i <= k; i ++) {
int x;
cin >> x;
s.insert(mp(0, x));
d[x] = 0;
}
while (s.size()) {
int v = s.begin() -> S;
s.erase(s.begin());
for (auto to : g[v]) {
if (d[to.F] > d[v] + to.S) {
s.erase(mp(d[to.F], to.F));
d[to.F] = d[v] + to.S;
s.insert(mp(d[to.F], to.F));
}
}
}
for (auto &it : all) {
it.F = min(d[it.S.F], d[it.S.S]);
}
sort(every(all));
reverse(every(all));
for (auto it : all) {
if (uni(it.S.F, it.S.S)) {
gr[it.S.F].pb(mp(it.S.S, it.F));
gr[it.S.S].pb(mp(it.S.F, it.F));
// cout << it.S.F << ' ' << it.S.S << ' ' << << '\n';
}
}
dfs (1);
int q;
cin >> q;
while (q -- ) {
int l, r;
cin >> l >> r;
int x = lca(l, r);
// cout << x << ' ' << l << ' ' << r << " query " << get(l, x) << ' ' << get(r, x) << ' ' ;
cout << min(get(l, x), get(r, x)) << '\n';
}
return Accepted;
}
// Coded By OB
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
28536 KB |
Output is correct |
2 |
Correct |
30 ms |
28920 KB |
Output is correct |
3 |
Correct |
29 ms |
28920 KB |
Output is correct |
4 |
Correct |
27 ms |
28536 KB |
Output is correct |
5 |
Correct |
29 ms |
28920 KB |
Output is correct |
6 |
Correct |
29 ms |
28792 KB |
Output is correct |
7 |
Correct |
27 ms |
28536 KB |
Output is correct |
8 |
Correct |
27 ms |
28664 KB |
Output is correct |
9 |
Correct |
29 ms |
28912 KB |
Output is correct |
10 |
Correct |
29 ms |
28920 KB |
Output is correct |
11 |
Correct |
29 ms |
28920 KB |
Output is correct |
12 |
Correct |
29 ms |
28920 KB |
Output is correct |
13 |
Correct |
29 ms |
28920 KB |
Output is correct |
14 |
Correct |
29 ms |
28792 KB |
Output is correct |
15 |
Correct |
29 ms |
28924 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
28536 KB |
Output is correct |
2 |
Correct |
30 ms |
28920 KB |
Output is correct |
3 |
Correct |
29 ms |
28920 KB |
Output is correct |
4 |
Correct |
27 ms |
28536 KB |
Output is correct |
5 |
Correct |
29 ms |
28920 KB |
Output is correct |
6 |
Correct |
29 ms |
28792 KB |
Output is correct |
7 |
Correct |
27 ms |
28536 KB |
Output is correct |
8 |
Correct |
27 ms |
28664 KB |
Output is correct |
9 |
Correct |
29 ms |
28912 KB |
Output is correct |
10 |
Correct |
29 ms |
28920 KB |
Output is correct |
11 |
Correct |
29 ms |
28920 KB |
Output is correct |
12 |
Correct |
29 ms |
28920 KB |
Output is correct |
13 |
Correct |
29 ms |
28920 KB |
Output is correct |
14 |
Correct |
29 ms |
28792 KB |
Output is correct |
15 |
Correct |
29 ms |
28924 KB |
Output is correct |
16 |
Correct |
291 ms |
51400 KB |
Output is correct |
17 |
Correct |
836 ms |
70452 KB |
Output is correct |
18 |
Correct |
79 ms |
33456 KB |
Output is correct |
19 |
Correct |
242 ms |
58396 KB |
Output is correct |
20 |
Correct |
785 ms |
71192 KB |
Output is correct |
21 |
Correct |
439 ms |
60368 KB |
Output is correct |
22 |
Correct |
255 ms |
61228 KB |
Output is correct |
23 |
Correct |
833 ms |
71300 KB |
Output is correct |
24 |
Correct |
841 ms |
71340 KB |
Output is correct |
25 |
Correct |
822 ms |
71184 KB |
Output is correct |
26 |
Correct |
249 ms |
58248 KB |
Output is correct |
27 |
Correct |
249 ms |
58240 KB |
Output is correct |
28 |
Correct |
247 ms |
58140 KB |
Output is correct |
29 |
Correct |
244 ms |
58272 KB |
Output is correct |
30 |
Correct |
259 ms |
58320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
28536 KB |
Output is correct |
2 |
Correct |
27 ms |
28540 KB |
Output is correct |
3 |
Correct |
27 ms |
28536 KB |
Output is correct |
4 |
Correct |
28 ms |
28636 KB |
Output is correct |
5 |
Correct |
26 ms |
28540 KB |
Output is correct |
6 |
Correct |
27 ms |
28536 KB |
Output is correct |
7 |
Correct |
26 ms |
28536 KB |
Output is correct |
8 |
Correct |
27 ms |
28632 KB |
Output is correct |
9 |
Correct |
26 ms |
28636 KB |
Output is correct |
10 |
Correct |
26 ms |
28636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
392 ms |
59568 KB |
Output is correct |
2 |
Correct |
728 ms |
70040 KB |
Output is correct |
3 |
Correct |
730 ms |
70040 KB |
Output is correct |
4 |
Correct |
194 ms |
58152 KB |
Output is correct |
5 |
Correct |
723 ms |
70120 KB |
Output is correct |
6 |
Correct |
703 ms |
70044 KB |
Output is correct |
7 |
Correct |
717 ms |
69948 KB |
Output is correct |
8 |
Correct |
718 ms |
70008 KB |
Output is correct |
9 |
Correct |
733 ms |
69992 KB |
Output is correct |
10 |
Correct |
740 ms |
69988 KB |
Output is correct |
11 |
Correct |
723 ms |
70112 KB |
Output is correct |
12 |
Correct |
747 ms |
70244 KB |
Output is correct |
13 |
Correct |
726 ms |
70180 KB |
Output is correct |
14 |
Correct |
723 ms |
70120 KB |
Output is correct |
15 |
Correct |
743 ms |
70232 KB |
Output is correct |
16 |
Correct |
736 ms |
70096 KB |
Output is correct |
17 |
Correct |
719 ms |
70132 KB |
Output is correct |
18 |
Correct |
707 ms |
70136 KB |
Output is correct |
19 |
Correct |
190 ms |
59880 KB |
Output is correct |
20 |
Correct |
707 ms |
70076 KB |
Output is correct |
21 |
Correct |
656 ms |
70736 KB |
Output is correct |
22 |
Correct |
192 ms |
57800 KB |
Output is correct |
23 |
Correct |
205 ms |
56920 KB |
Output is correct |
24 |
Correct |
187 ms |
57744 KB |
Output is correct |
25 |
Correct |
193 ms |
57744 KB |
Output is correct |
26 |
Correct |
222 ms |
57256 KB |
Output is correct |
27 |
Correct |
205 ms |
59700 KB |
Output is correct |
28 |
Correct |
192 ms |
57816 KB |
Output is correct |
29 |
Correct |
203 ms |
59048 KB |
Output is correct |
30 |
Correct |
190 ms |
57752 KB |
Output is correct |
31 |
Correct |
240 ms |
58980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
28536 KB |
Output is correct |
2 |
Correct |
30 ms |
28920 KB |
Output is correct |
3 |
Correct |
29 ms |
28920 KB |
Output is correct |
4 |
Correct |
27 ms |
28536 KB |
Output is correct |
5 |
Correct |
29 ms |
28920 KB |
Output is correct |
6 |
Correct |
29 ms |
28792 KB |
Output is correct |
7 |
Correct |
27 ms |
28536 KB |
Output is correct |
8 |
Correct |
27 ms |
28664 KB |
Output is correct |
9 |
Correct |
29 ms |
28912 KB |
Output is correct |
10 |
Correct |
29 ms |
28920 KB |
Output is correct |
11 |
Correct |
29 ms |
28920 KB |
Output is correct |
12 |
Correct |
29 ms |
28920 KB |
Output is correct |
13 |
Correct |
29 ms |
28920 KB |
Output is correct |
14 |
Correct |
29 ms |
28792 KB |
Output is correct |
15 |
Correct |
29 ms |
28924 KB |
Output is correct |
16 |
Correct |
291 ms |
51400 KB |
Output is correct |
17 |
Correct |
836 ms |
70452 KB |
Output is correct |
18 |
Correct |
79 ms |
33456 KB |
Output is correct |
19 |
Correct |
242 ms |
58396 KB |
Output is correct |
20 |
Correct |
785 ms |
71192 KB |
Output is correct |
21 |
Correct |
439 ms |
60368 KB |
Output is correct |
22 |
Correct |
255 ms |
61228 KB |
Output is correct |
23 |
Correct |
833 ms |
71300 KB |
Output is correct |
24 |
Correct |
841 ms |
71340 KB |
Output is correct |
25 |
Correct |
822 ms |
71184 KB |
Output is correct |
26 |
Correct |
249 ms |
58248 KB |
Output is correct |
27 |
Correct |
249 ms |
58240 KB |
Output is correct |
28 |
Correct |
247 ms |
58140 KB |
Output is correct |
29 |
Correct |
244 ms |
58272 KB |
Output is correct |
30 |
Correct |
259 ms |
58320 KB |
Output is correct |
31 |
Correct |
27 ms |
28536 KB |
Output is correct |
32 |
Correct |
27 ms |
28540 KB |
Output is correct |
33 |
Correct |
27 ms |
28536 KB |
Output is correct |
34 |
Correct |
28 ms |
28636 KB |
Output is correct |
35 |
Correct |
26 ms |
28540 KB |
Output is correct |
36 |
Correct |
27 ms |
28536 KB |
Output is correct |
37 |
Correct |
26 ms |
28536 KB |
Output is correct |
38 |
Correct |
27 ms |
28632 KB |
Output is correct |
39 |
Correct |
26 ms |
28636 KB |
Output is correct |
40 |
Correct |
26 ms |
28636 KB |
Output is correct |
41 |
Correct |
392 ms |
59568 KB |
Output is correct |
42 |
Correct |
728 ms |
70040 KB |
Output is correct |
43 |
Correct |
730 ms |
70040 KB |
Output is correct |
44 |
Correct |
194 ms |
58152 KB |
Output is correct |
45 |
Correct |
723 ms |
70120 KB |
Output is correct |
46 |
Correct |
703 ms |
70044 KB |
Output is correct |
47 |
Correct |
717 ms |
69948 KB |
Output is correct |
48 |
Correct |
718 ms |
70008 KB |
Output is correct |
49 |
Correct |
733 ms |
69992 KB |
Output is correct |
50 |
Correct |
740 ms |
69988 KB |
Output is correct |
51 |
Correct |
723 ms |
70112 KB |
Output is correct |
52 |
Correct |
747 ms |
70244 KB |
Output is correct |
53 |
Correct |
726 ms |
70180 KB |
Output is correct |
54 |
Correct |
723 ms |
70120 KB |
Output is correct |
55 |
Correct |
743 ms |
70232 KB |
Output is correct |
56 |
Correct |
736 ms |
70096 KB |
Output is correct |
57 |
Correct |
719 ms |
70132 KB |
Output is correct |
58 |
Correct |
707 ms |
70136 KB |
Output is correct |
59 |
Correct |
190 ms |
59880 KB |
Output is correct |
60 |
Correct |
707 ms |
70076 KB |
Output is correct |
61 |
Correct |
656 ms |
70736 KB |
Output is correct |
62 |
Correct |
192 ms |
57800 KB |
Output is correct |
63 |
Correct |
205 ms |
56920 KB |
Output is correct |
64 |
Correct |
187 ms |
57744 KB |
Output is correct |
65 |
Correct |
193 ms |
57744 KB |
Output is correct |
66 |
Correct |
222 ms |
57256 KB |
Output is correct |
67 |
Correct |
205 ms |
59700 KB |
Output is correct |
68 |
Correct |
192 ms |
57816 KB |
Output is correct |
69 |
Correct |
203 ms |
59048 KB |
Output is correct |
70 |
Correct |
190 ms |
57752 KB |
Output is correct |
71 |
Correct |
240 ms |
58980 KB |
Output is correct |
72 |
Correct |
470 ms |
61296 KB |
Output is correct |
73 |
Correct |
846 ms |
71968 KB |
Output is correct |
74 |
Correct |
824 ms |
71884 KB |
Output is correct |
75 |
Correct |
818 ms |
72004 KB |
Output is correct |
76 |
Correct |
820 ms |
71524 KB |
Output is correct |
77 |
Correct |
854 ms |
71780 KB |
Output is correct |
78 |
Correct |
814 ms |
71836 KB |
Output is correct |
79 |
Correct |
827 ms |
71844 KB |
Output is correct |
80 |
Correct |
837 ms |
71712 KB |
Output is correct |
81 |
Correct |
854 ms |
72000 KB |
Output is correct |
82 |
Correct |
839 ms |
71576 KB |
Output is correct |
83 |
Correct |
821 ms |
71628 KB |
Output is correct |
84 |
Correct |
851 ms |
71832 KB |
Output is correct |
85 |
Correct |
832 ms |
70780 KB |
Output is correct |
86 |
Correct |
839 ms |
70676 KB |
Output is correct |
87 |
Correct |
840 ms |
70736 KB |
Output is correct |
88 |
Correct |
828 ms |
71904 KB |
Output is correct |
89 |
Correct |
326 ms |
60872 KB |
Output is correct |
90 |
Correct |
840 ms |
72188 KB |
Output is correct |
91 |
Correct |
758 ms |
72476 KB |
Output is correct |
92 |
Correct |
275 ms |
58780 KB |
Output is correct |
93 |
Correct |
321 ms |
58544 KB |
Output is correct |
94 |
Correct |
277 ms |
58960 KB |
Output is correct |
95 |
Correct |
270 ms |
59164 KB |
Output is correct |
96 |
Correct |
337 ms |
58280 KB |
Output is correct |
97 |
Correct |
345 ms |
59932 KB |
Output is correct |
98 |
Correct |
276 ms |
59192 KB |
Output is correct |
99 |
Correct |
326 ms |
61292 KB |
Output is correct |
100 |
Correct |
274 ms |
58832 KB |
Output is correct |