#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
using namespace std;
typedef long long ll;
const int LG = 20;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int INF = 1e9;
const double PI = acos(-1.0);
struct item {
int w, x, y;
};
vector < tuple < int, int, int > > e;
int n, m, k, q, p[N], lvl[N], up[N][LG + 5], mn[N][LG + 5];
int d[N];
vector < pair < int, int > > g[N], g1[N];
int get(int v) {
return (v == p[v] ? v : p[v] = get(p[v]));
}
inline void unite(int v, int u) {
v = get(v);
u = get(u);
if (rand() & 1)
swap(v, u);
if (v != u)
p[u] = v;
}
int solve(int s, int t) {
if (lvl[s] < lvl[t])
swap(s, t);
int ans = min(d[s], d[t]);
for (int i = LG; i >= 0; --i) {
if (lvl[up[s][i]] >= lvl[t]) {
ans = min(mn[s][i], ans);
s = up[s][i];
}
}
if (s == t)
return ans;
for (int i = LG; i >= 0; --i) {
if (up[s][i] != up[t][i]) {
ans = min(mn[s][i], ans);
ans = min(mn[t][i], ans);
s = up[s][i];
t = up[t][i];
}
}
return min({ans, mn[s][0], mn[t][0]});
}
inline void dfs(int v, int p = 0, int len = INF) {
up[v][0] = p;
mn[v][0] = len;
lvl[v] = lvl[p] + 1;
for (int i = 1; i <= LG; ++i) {
up[v][i] = up[up[v][i - 1]][i - 1];
mn[v][i] = min(mn[v][i - 1], mn[up[v][i - 1]][i - 1]);
}
for (auto node : g1[v]) {
int to = node.first, lenn = node.second;
if (p != to)
dfs(to, v, lenn);
}
}
int main() {
srand(time(NULL));
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
d[i] = INF;
p[i] = i;
for (int j = 0; j <= LG; ++j)
mn[i][j] = INF;
}
for (int i = 1; i <= m; ++i) {
int u, v, w;
cin >> u >> v >> w;
g[v].push_back({u, w});
g[u].push_back({v, w});
}
cin >> k;
set < pair < int, int > > st;
for (int i = 1, x; i <= k; ++i) {
cin >> x;
d[x] = 0;
st.insert({0, x});
}
while (!st.empty()) {
int x = (*st.begin()).second;
st.erase(st.begin());
for (auto node : g[x]) {
int to = node.first, len = node.second;
if (d[to] > d[x] + len) {
st.erase({d[to], to});
d[to] = d[x] + len;
st.insert({d[to], to});
}
}
}
for (int i = 1; i <= n; ++i) {
for (auto node : g[i]) {
int to = node.first;
e.push_back(make_tuple(-1 * min(d[to], d[i]), i, to));
}
}
sort(e.begin(), e.end());
for (auto ver : e) {
int x, y, w;
tie(w, x, y) = ver;
w *= -1;
if (get(x) != get(y)) {
g1[x].push_back({y, w});
g1[y].push_back({x, w});
unite(x, y);
}
}
dfs(1);
cin >> q;
for (int i = 1; i <= q; ++i) {
int s, t;
cin >> s >> t;
cout << solve(s, t) << "\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
9720 KB |
Output is correct |
2 |
Correct |
17 ms |
10020 KB |
Output is correct |
3 |
Correct |
17 ms |
9980 KB |
Output is correct |
4 |
Correct |
11 ms |
9720 KB |
Output is correct |
5 |
Correct |
17 ms |
10076 KB |
Output is correct |
6 |
Correct |
17 ms |
10028 KB |
Output is correct |
7 |
Correct |
12 ms |
9848 KB |
Output is correct |
8 |
Correct |
12 ms |
9720 KB |
Output is correct |
9 |
Correct |
17 ms |
9976 KB |
Output is correct |
10 |
Correct |
17 ms |
10104 KB |
Output is correct |
11 |
Correct |
17 ms |
9976 KB |
Output is correct |
12 |
Correct |
22 ms |
10020 KB |
Output is correct |
13 |
Correct |
17 ms |
9976 KB |
Output is correct |
14 |
Correct |
17 ms |
10108 KB |
Output is correct |
15 |
Correct |
17 ms |
9980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
9720 KB |
Output is correct |
2 |
Correct |
17 ms |
10020 KB |
Output is correct |
3 |
Correct |
17 ms |
9980 KB |
Output is correct |
4 |
Correct |
11 ms |
9720 KB |
Output is correct |
5 |
Correct |
17 ms |
10076 KB |
Output is correct |
6 |
Correct |
17 ms |
10028 KB |
Output is correct |
7 |
Correct |
12 ms |
9848 KB |
Output is correct |
8 |
Correct |
12 ms |
9720 KB |
Output is correct |
9 |
Correct |
17 ms |
9976 KB |
Output is correct |
10 |
Correct |
17 ms |
10104 KB |
Output is correct |
11 |
Correct |
17 ms |
9976 KB |
Output is correct |
12 |
Correct |
22 ms |
10020 KB |
Output is correct |
13 |
Correct |
17 ms |
9976 KB |
Output is correct |
14 |
Correct |
17 ms |
10108 KB |
Output is correct |
15 |
Correct |
17 ms |
9980 KB |
Output is correct |
16 |
Correct |
743 ms |
34860 KB |
Output is correct |
17 |
Correct |
1904 ms |
59068 KB |
Output is correct |
18 |
Correct |
144 ms |
14920 KB |
Output is correct |
19 |
Correct |
709 ms |
41604 KB |
Output is correct |
20 |
Correct |
1877 ms |
59056 KB |
Output is correct |
21 |
Correct |
1052 ms |
45060 KB |
Output is correct |
22 |
Correct |
731 ms |
43112 KB |
Output is correct |
23 |
Correct |
1831 ms |
59024 KB |
Output is correct |
24 |
Correct |
1816 ms |
59064 KB |
Output is correct |
25 |
Correct |
1827 ms |
59024 KB |
Output is correct |
26 |
Correct |
693 ms |
41396 KB |
Output is correct |
27 |
Correct |
714 ms |
41452 KB |
Output is correct |
28 |
Correct |
707 ms |
41612 KB |
Output is correct |
29 |
Correct |
703 ms |
41536 KB |
Output is correct |
30 |
Correct |
713 ms |
41724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
9720 KB |
Output is correct |
2 |
Correct |
11 ms |
9720 KB |
Output is correct |
3 |
Correct |
11 ms |
9720 KB |
Output is correct |
4 |
Correct |
12 ms |
9720 KB |
Output is correct |
5 |
Correct |
11 ms |
9720 KB |
Output is correct |
6 |
Correct |
11 ms |
9720 KB |
Output is correct |
7 |
Correct |
11 ms |
9720 KB |
Output is correct |
8 |
Correct |
12 ms |
9720 KB |
Output is correct |
9 |
Correct |
11 ms |
9720 KB |
Output is correct |
10 |
Correct |
11 ms |
9724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
628 ms |
44720 KB |
Output is correct |
2 |
Correct |
1419 ms |
58556 KB |
Output is correct |
3 |
Correct |
1409 ms |
58700 KB |
Output is correct |
4 |
Correct |
309 ms |
40956 KB |
Output is correct |
5 |
Correct |
1442 ms |
58564 KB |
Output is correct |
6 |
Correct |
1416 ms |
58488 KB |
Output is correct |
7 |
Correct |
1426 ms |
58664 KB |
Output is correct |
8 |
Correct |
1401 ms |
58520 KB |
Output is correct |
9 |
Correct |
1404 ms |
58508 KB |
Output is correct |
10 |
Correct |
1406 ms |
58648 KB |
Output is correct |
11 |
Correct |
1417 ms |
58636 KB |
Output is correct |
12 |
Correct |
1404 ms |
58480 KB |
Output is correct |
13 |
Correct |
1395 ms |
58596 KB |
Output is correct |
14 |
Correct |
1421 ms |
58544 KB |
Output is correct |
15 |
Correct |
1427 ms |
58688 KB |
Output is correct |
16 |
Correct |
1391 ms |
58512 KB |
Output is correct |
17 |
Correct |
1422 ms |
58552 KB |
Output is correct |
18 |
Correct |
1403 ms |
58620 KB |
Output is correct |
19 |
Correct |
315 ms |
42104 KB |
Output is correct |
20 |
Correct |
1388 ms |
58508 KB |
Output is correct |
21 |
Correct |
1296 ms |
58628 KB |
Output is correct |
22 |
Correct |
294 ms |
41104 KB |
Output is correct |
23 |
Correct |
313 ms |
40396 KB |
Output is correct |
24 |
Correct |
297 ms |
41068 KB |
Output is correct |
25 |
Correct |
298 ms |
41348 KB |
Output is correct |
26 |
Correct |
332 ms |
40640 KB |
Output is correct |
27 |
Correct |
309 ms |
41952 KB |
Output is correct |
28 |
Correct |
296 ms |
41128 KB |
Output is correct |
29 |
Correct |
317 ms |
41460 KB |
Output is correct |
30 |
Correct |
300 ms |
41480 KB |
Output is correct |
31 |
Correct |
315 ms |
41536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
9720 KB |
Output is correct |
2 |
Correct |
17 ms |
10020 KB |
Output is correct |
3 |
Correct |
17 ms |
9980 KB |
Output is correct |
4 |
Correct |
11 ms |
9720 KB |
Output is correct |
5 |
Correct |
17 ms |
10076 KB |
Output is correct |
6 |
Correct |
17 ms |
10028 KB |
Output is correct |
7 |
Correct |
12 ms |
9848 KB |
Output is correct |
8 |
Correct |
12 ms |
9720 KB |
Output is correct |
9 |
Correct |
17 ms |
9976 KB |
Output is correct |
10 |
Correct |
17 ms |
10104 KB |
Output is correct |
11 |
Correct |
17 ms |
9976 KB |
Output is correct |
12 |
Correct |
22 ms |
10020 KB |
Output is correct |
13 |
Correct |
17 ms |
9976 KB |
Output is correct |
14 |
Correct |
17 ms |
10108 KB |
Output is correct |
15 |
Correct |
17 ms |
9980 KB |
Output is correct |
16 |
Correct |
743 ms |
34860 KB |
Output is correct |
17 |
Correct |
1904 ms |
59068 KB |
Output is correct |
18 |
Correct |
144 ms |
14920 KB |
Output is correct |
19 |
Correct |
709 ms |
41604 KB |
Output is correct |
20 |
Correct |
1877 ms |
59056 KB |
Output is correct |
21 |
Correct |
1052 ms |
45060 KB |
Output is correct |
22 |
Correct |
731 ms |
43112 KB |
Output is correct |
23 |
Correct |
1831 ms |
59024 KB |
Output is correct |
24 |
Correct |
1816 ms |
59064 KB |
Output is correct |
25 |
Correct |
1827 ms |
59024 KB |
Output is correct |
26 |
Correct |
693 ms |
41396 KB |
Output is correct |
27 |
Correct |
714 ms |
41452 KB |
Output is correct |
28 |
Correct |
707 ms |
41612 KB |
Output is correct |
29 |
Correct |
703 ms |
41536 KB |
Output is correct |
30 |
Correct |
713 ms |
41724 KB |
Output is correct |
31 |
Correct |
11 ms |
9720 KB |
Output is correct |
32 |
Correct |
11 ms |
9720 KB |
Output is correct |
33 |
Correct |
11 ms |
9720 KB |
Output is correct |
34 |
Correct |
12 ms |
9720 KB |
Output is correct |
35 |
Correct |
11 ms |
9720 KB |
Output is correct |
36 |
Correct |
11 ms |
9720 KB |
Output is correct |
37 |
Correct |
11 ms |
9720 KB |
Output is correct |
38 |
Correct |
12 ms |
9720 KB |
Output is correct |
39 |
Correct |
11 ms |
9720 KB |
Output is correct |
40 |
Correct |
11 ms |
9724 KB |
Output is correct |
41 |
Correct |
628 ms |
44720 KB |
Output is correct |
42 |
Correct |
1419 ms |
58556 KB |
Output is correct |
43 |
Correct |
1409 ms |
58700 KB |
Output is correct |
44 |
Correct |
309 ms |
40956 KB |
Output is correct |
45 |
Correct |
1442 ms |
58564 KB |
Output is correct |
46 |
Correct |
1416 ms |
58488 KB |
Output is correct |
47 |
Correct |
1426 ms |
58664 KB |
Output is correct |
48 |
Correct |
1401 ms |
58520 KB |
Output is correct |
49 |
Correct |
1404 ms |
58508 KB |
Output is correct |
50 |
Correct |
1406 ms |
58648 KB |
Output is correct |
51 |
Correct |
1417 ms |
58636 KB |
Output is correct |
52 |
Correct |
1404 ms |
58480 KB |
Output is correct |
53 |
Correct |
1395 ms |
58596 KB |
Output is correct |
54 |
Correct |
1421 ms |
58544 KB |
Output is correct |
55 |
Correct |
1427 ms |
58688 KB |
Output is correct |
56 |
Correct |
1391 ms |
58512 KB |
Output is correct |
57 |
Correct |
1422 ms |
58552 KB |
Output is correct |
58 |
Correct |
1403 ms |
58620 KB |
Output is correct |
59 |
Correct |
315 ms |
42104 KB |
Output is correct |
60 |
Correct |
1388 ms |
58508 KB |
Output is correct |
61 |
Correct |
1296 ms |
58628 KB |
Output is correct |
62 |
Correct |
294 ms |
41104 KB |
Output is correct |
63 |
Correct |
313 ms |
40396 KB |
Output is correct |
64 |
Correct |
297 ms |
41068 KB |
Output is correct |
65 |
Correct |
298 ms |
41348 KB |
Output is correct |
66 |
Correct |
332 ms |
40640 KB |
Output is correct |
67 |
Correct |
309 ms |
41952 KB |
Output is correct |
68 |
Correct |
296 ms |
41128 KB |
Output is correct |
69 |
Correct |
317 ms |
41460 KB |
Output is correct |
70 |
Correct |
300 ms |
41480 KB |
Output is correct |
71 |
Correct |
315 ms |
41536 KB |
Output is correct |
72 |
Correct |
1094 ms |
45188 KB |
Output is correct |
73 |
Correct |
1883 ms |
59256 KB |
Output is correct |
74 |
Correct |
1848 ms |
59200 KB |
Output is correct |
75 |
Correct |
1864 ms |
59380 KB |
Output is correct |
76 |
Correct |
1860 ms |
59228 KB |
Output is correct |
77 |
Correct |
1861 ms |
59532 KB |
Output is correct |
78 |
Correct |
1861 ms |
59492 KB |
Output is correct |
79 |
Correct |
1830 ms |
59588 KB |
Output is correct |
80 |
Correct |
1858 ms |
59428 KB |
Output is correct |
81 |
Correct |
1852 ms |
59432 KB |
Output is correct |
82 |
Correct |
1866 ms |
59360 KB |
Output is correct |
83 |
Correct |
1864 ms |
59348 KB |
Output is correct |
84 |
Correct |
1869 ms |
59388 KB |
Output is correct |
85 |
Correct |
1876 ms |
59180 KB |
Output is correct |
86 |
Correct |
1861 ms |
59464 KB |
Output is correct |
87 |
Correct |
1839 ms |
59448 KB |
Output is correct |
88 |
Correct |
1898 ms |
59316 KB |
Output is correct |
89 |
Correct |
833 ms |
42680 KB |
Output is correct |
90 |
Correct |
1821 ms |
59252 KB |
Output is correct |
91 |
Correct |
1752 ms |
59268 KB |
Output is correct |
92 |
Correct |
724 ms |
41912 KB |
Output is correct |
93 |
Correct |
776 ms |
41488 KB |
Output is correct |
94 |
Correct |
718 ms |
41940 KB |
Output is correct |
95 |
Correct |
719 ms |
41700 KB |
Output is correct |
96 |
Correct |
788 ms |
41068 KB |
Output is correct |
97 |
Correct |
813 ms |
41972 KB |
Output is correct |
98 |
Correct |
724 ms |
41872 KB |
Output is correct |
99 |
Correct |
808 ms |
42792 KB |
Output is correct |
100 |
Correct |
719 ms |
41816 KB |
Output is correct |