// looking to shine brighter in this world...
#ifdef LOCAL
#include "local_header.h"
#include "debugger.h"
#else
#include <bits/stdc++.h>
#define debug(...)
#define DB(...)
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif
using namespace std;
static const bool __initialization = [] {
cin.tie(nullptr)->sync_with_stdio(false);
#define TASK "NPP"
if (fopen(TASK".inp", "r")) {
(void)(!freopen(TASK".inp", "r", stdin));
(void)(!freopen(TASK".out", "w", stdout)); }
cout << setprecision(12) << fixed;
return true;
}();
using ll = long long;
using ld = long double;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fi first
#define se second
#define For(i, l, r) for (int i = (l); i <= (r); ++i)
#define Ford(i, r, l) for (int i = (r); i >= (l); --i)
#define Rep(i, n) For (i, 0, (n) - 1)
#define Repd(i, n) Ford (i, (n) - 1, 0)
#define Fe(...) for (const auto& __VA_ARGS__)
#define Fa(...) for (auto __VA_ARGS__)
template <class C> inline int isz(const C& c) { return static_cast<int>(c.size()); }
template <class T> inline bool chmin(T& a, const T& b) { return (a > b) ? a = b, true : false; }
template <class T> inline bool chmax(T& a, const T& b) { return (a < b) ? a = b, true : false; }
constexpr ld eps = 1e-9;
constexpr int inf = 1e9;
constexpr ll linf = 1e18;
// =============================================================================
constexpr int maxn = 1e5 + 5;
constexpr int logn = 20;
using P = pair<int, int>;
struct E {
int u, v, c;
bool operator<(const E& o) const {
return c < o.c;
}
};
struct Dsu {
int par[maxn];
Dsu() {
memset(par, -1, sizeof(par));
}
int find(int x) {
return (par[x] < 0) ? x : par[x] = find(par[x]);
}
bool merge(int u, int v) {
u = find(u), v = find(v);
if (u == v) return false;
if (par[v] < par[u]) swap(u, v);
par[u] += par[v];
par[v] = u;
return true;
}
};
int n, ne, nq;
vector<P> g[maxn];
int nk;
int src[maxn];
int d[maxn];
priority_queue<P, vector<P>, greater<P>> q;
vector<E> e;
Dsu dsu;
vector<P> tree[maxn];
int up[maxn][logn];
int dist[maxn][logn];
int dep[maxn];
void addEdge(int u, int v, int c) {
tree[u].emplace_back(v, c);
tree[v].emplace_back(u, c);
}
void Dfs(int u) {
Fe ([v, c] : tree[u]) {
if (v == up[u][0]) continue;
up[v][0] = u;
dist[v][0] = c;
dep[v] = dep[u] + 1;
Dfs(v);
}
}
int getDist(int u, int v) {
if (u == v) return 0;
int ret = inf;
if (dep[u] < dep[v]) swap(u, v);
int diff = dep[u] - dep[v];
Repd (i, logn) {
if (diff >> i & 1) {
chmin(ret, dist[u][i]);
u = up[u][i];
}
}
if (u == v) return ret;
Repd (i, logn) {
if (up[u][i] != up[v][i]) {
chmin(ret, dist[u][i]);
chmin(ret, dist[v][i]);
u = up[u][i];
v = up[v][i];
}
}
return min({ret, dist[u][0], dist[v][0]});
}
signed main() {
cin >> n >> ne;
Rep (_, ne) {
int u, v, c; cin >> u >> v >> c;
g[u].emplace_back(v, c);
g[v].emplace_back(u, c);
}
memset(d, 0x3f, sizeof(d));
cin >> nk;
For (i, 1, nk) {
cin >> src[i];
d[src[i]] = 0;
q.emplace(0, src[i]);
}
sort(src + 1, src + nk + 1);
while (isz(q)) {
auto [du, u] = q.top(); q.pop();
if (du != d[u]) continue;
Fe ([v, c] : g[u]) {
if (chmin(d[v], d[u] + c)) {
q.emplace(d[v], v);
}
}
}
e.reserve(ne);
For (u, 1, n) {
if (binary_search(src + 1, src + nk + 1, u)) {
continue;
}
Fe ([v, c] : g[u]) {
if (u >= v) continue;
if (!binary_search(src + 1, src + nk + 1, v)) {
e.push_back({u, v, min(d[u], d[v])});
}
}
}
sort(rall(e));
Fe ([u, v, c] : e) {
if (dsu.merge(u, v)) {
addEdge(u, v, c);
}
}
int root = n + 1;
For (i, 1, n) {
if (dsu.merge(root, i)) {
addEdge(root, i, 0);
}
}
For (i, 1, nk) {
if (dsu.merge(root, src[i])) {
addEdge(root, src[i], 0);
}
}
Dfs(root);
For (j, 1, logn - 1) {
For (i, 1, root) {
up[i][j] = up[up[i][j - 1]][j - 1];
dist[i][j] = min(dist[i][j - 1], dist[up[i][j - 1]][j - 1]);
}
}
cin >> nq;
Rep (_, nq) {
int u, v; cin >> u >> v;
cout << getDist(u, v) << '\n';
}
}
Compilation message
plan.cpp: In function 'void Dfs(int)':
plan.cpp:108:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
108 | Fe ([v, c] : tree[u]) {
| ^
plan.cpp:38:34: note: in definition of macro 'Fe'
38 | #define Fe(...) for (const auto& __VA_ARGS__)
| ^~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:168:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
168 | auto [du, u] = q.top(); q.pop();
| ^
plan.cpp:171:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
171 | Fe ([v, c] : g[u]) {
| ^
plan.cpp:38:34: note: in definition of macro 'Fe'
38 | #define Fe(...) for (const auto& __VA_ARGS__)
| ^~~~~~~~~~~
plan.cpp:185:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
185 | Fe ([v, c] : g[u]) {
| ^
plan.cpp:38:34: note: in definition of macro 'Fe'
38 | #define Fe(...) for (const auto& __VA_ARGS__)
| ^~~~~~~~~~~
plan.cpp:196:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
196 | Fe ([u, v, c] : e) {
| ^
plan.cpp:38:34: note: in definition of macro 'Fe'
38 | #define Fe(...) for (const auto& __VA_ARGS__)
| ^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5792 KB |
Output is correct |
2 |
Correct |
5 ms |
6048 KB |
Output is correct |
3 |
Correct |
5 ms |
6056 KB |
Output is correct |
4 |
Correct |
3 ms |
5808 KB |
Output is correct |
5 |
Correct |
4 ms |
6092 KB |
Output is correct |
6 |
Correct |
4 ms |
6052 KB |
Output is correct |
7 |
Correct |
3 ms |
5800 KB |
Output is correct |
8 |
Correct |
4 ms |
5804 KB |
Output is correct |
9 |
Correct |
5 ms |
5960 KB |
Output is correct |
10 |
Correct |
4 ms |
6060 KB |
Output is correct |
11 |
Correct |
4 ms |
6100 KB |
Output is correct |
12 |
Correct |
6 ms |
6048 KB |
Output is correct |
13 |
Correct |
7 ms |
6092 KB |
Output is correct |
14 |
Correct |
4 ms |
6068 KB |
Output is correct |
15 |
Correct |
4 ms |
6092 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5792 KB |
Output is correct |
2 |
Correct |
5 ms |
6048 KB |
Output is correct |
3 |
Correct |
5 ms |
6056 KB |
Output is correct |
4 |
Correct |
3 ms |
5808 KB |
Output is correct |
5 |
Correct |
4 ms |
6092 KB |
Output is correct |
6 |
Correct |
4 ms |
6052 KB |
Output is correct |
7 |
Correct |
3 ms |
5800 KB |
Output is correct |
8 |
Correct |
4 ms |
5804 KB |
Output is correct |
9 |
Correct |
5 ms |
5960 KB |
Output is correct |
10 |
Correct |
4 ms |
6060 KB |
Output is correct |
11 |
Correct |
4 ms |
6100 KB |
Output is correct |
12 |
Correct |
6 ms |
6048 KB |
Output is correct |
13 |
Correct |
7 ms |
6092 KB |
Output is correct |
14 |
Correct |
4 ms |
6068 KB |
Output is correct |
15 |
Correct |
4 ms |
6092 KB |
Output is correct |
16 |
Correct |
183 ms |
29044 KB |
Output is correct |
17 |
Correct |
490 ms |
54576 KB |
Output is correct |
18 |
Correct |
36 ms |
10664 KB |
Output is correct |
19 |
Correct |
137 ms |
34820 KB |
Output is correct |
20 |
Correct |
519 ms |
54596 KB |
Output is correct |
21 |
Correct |
255 ms |
37668 KB |
Output is correct |
22 |
Correct |
167 ms |
37156 KB |
Output is correct |
23 |
Correct |
558 ms |
54676 KB |
Output is correct |
24 |
Correct |
464 ms |
54576 KB |
Output is correct |
25 |
Correct |
482 ms |
53580 KB |
Output is correct |
26 |
Correct |
190 ms |
34728 KB |
Output is correct |
27 |
Correct |
137 ms |
34816 KB |
Output is correct |
28 |
Correct |
179 ms |
34764 KB |
Output is correct |
29 |
Correct |
140 ms |
34728 KB |
Output is correct |
30 |
Correct |
160 ms |
34944 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5708 KB |
Output is correct |
2 |
Correct |
4 ms |
5792 KB |
Output is correct |
3 |
Correct |
5 ms |
5708 KB |
Output is correct |
4 |
Correct |
3 ms |
5804 KB |
Output is correct |
5 |
Correct |
3 ms |
5708 KB |
Output is correct |
6 |
Correct |
3 ms |
5708 KB |
Output is correct |
7 |
Correct |
3 ms |
5708 KB |
Output is correct |
8 |
Correct |
3 ms |
5708 KB |
Output is correct |
9 |
Correct |
3 ms |
5708 KB |
Output is correct |
10 |
Correct |
3 ms |
5708 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
220 ms |
37412 KB |
Output is correct |
2 |
Correct |
406 ms |
52888 KB |
Output is correct |
3 |
Correct |
448 ms |
52980 KB |
Output is correct |
4 |
Correct |
117 ms |
32448 KB |
Output is correct |
5 |
Correct |
417 ms |
52936 KB |
Output is correct |
6 |
Correct |
451 ms |
52984 KB |
Output is correct |
7 |
Correct |
455 ms |
52948 KB |
Output is correct |
8 |
Correct |
424 ms |
53232 KB |
Output is correct |
9 |
Correct |
425 ms |
52924 KB |
Output is correct |
10 |
Correct |
490 ms |
53004 KB |
Output is correct |
11 |
Correct |
405 ms |
52896 KB |
Output is correct |
12 |
Correct |
431 ms |
52952 KB |
Output is correct |
13 |
Correct |
490 ms |
52872 KB |
Output is correct |
14 |
Correct |
473 ms |
52708 KB |
Output is correct |
15 |
Correct |
425 ms |
52016 KB |
Output is correct |
16 |
Correct |
456 ms |
52920 KB |
Output is correct |
17 |
Correct |
474 ms |
52836 KB |
Output is correct |
18 |
Correct |
426 ms |
53028 KB |
Output is correct |
19 |
Correct |
124 ms |
34756 KB |
Output is correct |
20 |
Correct |
410 ms |
52976 KB |
Output is correct |
21 |
Correct |
347 ms |
48044 KB |
Output is correct |
22 |
Correct |
112 ms |
33164 KB |
Output is correct |
23 |
Correct |
132 ms |
32288 KB |
Output is correct |
24 |
Correct |
98 ms |
33208 KB |
Output is correct |
25 |
Correct |
111 ms |
33176 KB |
Output is correct |
26 |
Correct |
158 ms |
32040 KB |
Output is correct |
27 |
Correct |
124 ms |
32672 KB |
Output is correct |
28 |
Correct |
107 ms |
33152 KB |
Output is correct |
29 |
Correct |
124 ms |
31940 KB |
Output is correct |
30 |
Correct |
98 ms |
33192 KB |
Output is correct |
31 |
Correct |
113 ms |
32160 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5792 KB |
Output is correct |
2 |
Correct |
5 ms |
6048 KB |
Output is correct |
3 |
Correct |
5 ms |
6056 KB |
Output is correct |
4 |
Correct |
3 ms |
5808 KB |
Output is correct |
5 |
Correct |
4 ms |
6092 KB |
Output is correct |
6 |
Correct |
4 ms |
6052 KB |
Output is correct |
7 |
Correct |
3 ms |
5800 KB |
Output is correct |
8 |
Correct |
4 ms |
5804 KB |
Output is correct |
9 |
Correct |
5 ms |
5960 KB |
Output is correct |
10 |
Correct |
4 ms |
6060 KB |
Output is correct |
11 |
Correct |
4 ms |
6100 KB |
Output is correct |
12 |
Correct |
6 ms |
6048 KB |
Output is correct |
13 |
Correct |
7 ms |
6092 KB |
Output is correct |
14 |
Correct |
4 ms |
6068 KB |
Output is correct |
15 |
Correct |
4 ms |
6092 KB |
Output is correct |
16 |
Correct |
183 ms |
29044 KB |
Output is correct |
17 |
Correct |
490 ms |
54576 KB |
Output is correct |
18 |
Correct |
36 ms |
10664 KB |
Output is correct |
19 |
Correct |
137 ms |
34820 KB |
Output is correct |
20 |
Correct |
519 ms |
54596 KB |
Output is correct |
21 |
Correct |
255 ms |
37668 KB |
Output is correct |
22 |
Correct |
167 ms |
37156 KB |
Output is correct |
23 |
Correct |
558 ms |
54676 KB |
Output is correct |
24 |
Correct |
464 ms |
54576 KB |
Output is correct |
25 |
Correct |
482 ms |
53580 KB |
Output is correct |
26 |
Correct |
190 ms |
34728 KB |
Output is correct |
27 |
Correct |
137 ms |
34816 KB |
Output is correct |
28 |
Correct |
179 ms |
34764 KB |
Output is correct |
29 |
Correct |
140 ms |
34728 KB |
Output is correct |
30 |
Correct |
160 ms |
34944 KB |
Output is correct |
31 |
Correct |
4 ms |
5708 KB |
Output is correct |
32 |
Correct |
4 ms |
5792 KB |
Output is correct |
33 |
Correct |
5 ms |
5708 KB |
Output is correct |
34 |
Correct |
3 ms |
5804 KB |
Output is correct |
35 |
Correct |
3 ms |
5708 KB |
Output is correct |
36 |
Correct |
3 ms |
5708 KB |
Output is correct |
37 |
Correct |
3 ms |
5708 KB |
Output is correct |
38 |
Correct |
3 ms |
5708 KB |
Output is correct |
39 |
Correct |
3 ms |
5708 KB |
Output is correct |
40 |
Correct |
3 ms |
5708 KB |
Output is correct |
41 |
Correct |
220 ms |
37412 KB |
Output is correct |
42 |
Correct |
406 ms |
52888 KB |
Output is correct |
43 |
Correct |
448 ms |
52980 KB |
Output is correct |
44 |
Correct |
117 ms |
32448 KB |
Output is correct |
45 |
Correct |
417 ms |
52936 KB |
Output is correct |
46 |
Correct |
451 ms |
52984 KB |
Output is correct |
47 |
Correct |
455 ms |
52948 KB |
Output is correct |
48 |
Correct |
424 ms |
53232 KB |
Output is correct |
49 |
Correct |
425 ms |
52924 KB |
Output is correct |
50 |
Correct |
490 ms |
53004 KB |
Output is correct |
51 |
Correct |
405 ms |
52896 KB |
Output is correct |
52 |
Correct |
431 ms |
52952 KB |
Output is correct |
53 |
Correct |
490 ms |
52872 KB |
Output is correct |
54 |
Correct |
473 ms |
52708 KB |
Output is correct |
55 |
Correct |
425 ms |
52016 KB |
Output is correct |
56 |
Correct |
456 ms |
52920 KB |
Output is correct |
57 |
Correct |
474 ms |
52836 KB |
Output is correct |
58 |
Correct |
426 ms |
53028 KB |
Output is correct |
59 |
Correct |
124 ms |
34756 KB |
Output is correct |
60 |
Correct |
410 ms |
52976 KB |
Output is correct |
61 |
Correct |
347 ms |
48044 KB |
Output is correct |
62 |
Correct |
112 ms |
33164 KB |
Output is correct |
63 |
Correct |
132 ms |
32288 KB |
Output is correct |
64 |
Correct |
98 ms |
33208 KB |
Output is correct |
65 |
Correct |
111 ms |
33176 KB |
Output is correct |
66 |
Correct |
158 ms |
32040 KB |
Output is correct |
67 |
Correct |
124 ms |
32672 KB |
Output is correct |
68 |
Correct |
107 ms |
33152 KB |
Output is correct |
69 |
Correct |
124 ms |
31940 KB |
Output is correct |
70 |
Correct |
98 ms |
33192 KB |
Output is correct |
71 |
Correct |
113 ms |
32160 KB |
Output is correct |
72 |
Correct |
278 ms |
39000 KB |
Output is correct |
73 |
Correct |
461 ms |
54580 KB |
Output is correct |
74 |
Correct |
473 ms |
54724 KB |
Output is correct |
75 |
Correct |
498 ms |
54668 KB |
Output is correct |
76 |
Correct |
512 ms |
54608 KB |
Output is correct |
77 |
Correct |
491 ms |
54612 KB |
Output is correct |
78 |
Correct |
460 ms |
54608 KB |
Output is correct |
79 |
Correct |
494 ms |
54620 KB |
Output is correct |
80 |
Correct |
501 ms |
54532 KB |
Output is correct |
81 |
Correct |
504 ms |
54604 KB |
Output is correct |
82 |
Correct |
505 ms |
54624 KB |
Output is correct |
83 |
Correct |
512 ms |
54496 KB |
Output is correct |
84 |
Correct |
535 ms |
54180 KB |
Output is correct |
85 |
Correct |
499 ms |
53580 KB |
Output is correct |
86 |
Correct |
552 ms |
54500 KB |
Output is correct |
87 |
Correct |
503 ms |
54628 KB |
Output is correct |
88 |
Correct |
492 ms |
54584 KB |
Output is correct |
89 |
Correct |
264 ms |
36364 KB |
Output is correct |
90 |
Correct |
442 ms |
54560 KB |
Output is correct |
91 |
Correct |
402 ms |
49564 KB |
Output is correct |
92 |
Correct |
145 ms |
34724 KB |
Output is correct |
93 |
Correct |
215 ms |
34340 KB |
Output is correct |
94 |
Correct |
167 ms |
34744 KB |
Output is correct |
95 |
Correct |
152 ms |
34772 KB |
Output is correct |
96 |
Correct |
206 ms |
33712 KB |
Output is correct |
97 |
Correct |
230 ms |
34064 KB |
Output is correct |
98 |
Correct |
152 ms |
34664 KB |
Output is correct |
99 |
Correct |
243 ms |
34520 KB |
Output is correct |
100 |
Correct |
162 ms |
34776 KB |
Output is correct |