#include <bits/stdc++.h>
#define int long long
using namespace std;
#define file ""
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define getbit(x, i) (((x) >> (i)) & 1)
#define bit(x) (1LL << (x))
#define popcount __builtin_popcountll
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
return l + rd() % (r - l + 1);
}
const int N = 1e5 + 5;
const int mod = (int)1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int oo = 1e9;
const long long ooo = 1e18;
template<class X, class Y> bool mini(X &a, Y b) {
return a > b ? (a = b, true) : false;
}
template<class X, class Y> bool maxi(X &a, Y b) {
return a < b ? (a = b, true) : false;
}
void add(int &a, int b) {
a += b;
if (a >= mod) a -= mod;
if (a < 0) a += mod;
}
class DSU {
int n;
vector<int> e;
public:
DSU(int n) : n (n), e (n, -1) {};
int find(int x) {
return e[x] < 0 ? x : e[x] = find(e[x]);
}
bool unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return false;
if (e[x] > e[y]) swap(x, y);
e[x] += e[y];
e[y] = x;
return true;
}
};
struct edge {
int u, v, c;
edge(int _u, int _v, int _c = 0) {
u = _u;
v = _v;
c = _c;
}
bool operator < (const edge &a) const {
return c < a.c;
}
};
int n, m, k;
vector<pair<int, int> > g[N], adj[N];
vector<int> npp;
vector<edge> edges;
// dijkstra
int dis[N];
void dijkstra() {
for (auto [u, v, c] : edges) {
g[u].emplace_back(v, c);
g[v].emplace_back(u, c);
}
memset(dis, 0x3f3f3f, sizeof dis);
typedef pair<int, int> node;
priority_queue<node, vector<node>, greater<node> > q;
for (int u : npp) {
dis[u] = 0;
q.emplace(0, u);
}
while (q.size()) {
int du, u;
tie(du, u) = q.top(); q.pop();
if (du > dis[u]) continue;
for (auto [v, c] : g[u]) {
if (dis[u] + c < dis[v]) {
dis[v] = dis[u] + c;
q.emplace(dis[v], v);
}
}
}
}
void mst() {
for (auto &[u, v, c] : edges) {
c = min(dis[u], dis[v]);
// cout << u << ' ' << v << ' ' << c << '\n';
}
sort(all(edges));
reverse(all(edges));
DSU dsu(n + 5);
for (auto [u, v, c] : edges) {
if (dsu.unite(u, v)) {
adj[u].emplace_back(v, c);
adj[v].emplace_back(u, c);
}
}
}
// lca
int h[N], l[N];
int par[N][lg + 1], mn[N][lg + 1];
void dfs(int u, int p) {
for (auto [v, c] : adj[u]) if (v != p) {
h[v] = h[u] + 1;
par[v][0] = u;
mn[v][0] = c;
dfs(v, u);
}
}
int max_edge(int u, int v) {
int res = oo;
if (h[u] < h[v]) swap(u, v);
while (h[u] > h[v]) {
int i = (int) log2(h[u] - h[v]);
res = min(res, mn[u][i]);
u = par[u][i];
}
if (u == v) return res;
for (int i = lg; i >= 0; --i) if (par[u][i] != par[v][i]) {
res = min({res, mn[u][i], mn[v][i]});
u = par[u][i];
v = par[v][i];
}
res = min({res, mn[u][0], mn[v][0]});
return res;
}
void PrePathQuery() {
dfs(1, 0);
for (int j = 1; j <= lg; ++j) for (int i = 1; i <= n; ++i) {
par[i][j] = par[par[i][j - 1]][j - 1];
mn[i][j] = min(mn[par[i][j - 1]][j - 1], mn[i][j - 1]);
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
// freopen(file".inp", "r", stdin);
// freopen(file".out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int u, v, c;
cin >> u >> v >> c;
edges.emplace_back(u, v, c);
}
cin >> k;
for (int i = 1; i <= k; ++i) {
int x;
cin >> x;
npp.push_back(x);
}
dijkstra();
mst();
PrePathQuery();
int q;
cin >> q;
while (q--) {
int u, v;
cin >> u >> v;
cout << max_edge(u, v) << '\n';
}
return 0;
}
/*
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 |
2 ms |
9048 KB |
Output is correct |
2 |
Correct |
3 ms |
11352 KB |
Output is correct |
3 |
Correct |
3 ms |
11352 KB |
Output is correct |
4 |
Correct |
2 ms |
9052 KB |
Output is correct |
5 |
Correct |
3 ms |
11356 KB |
Output is correct |
6 |
Correct |
3 ms |
11356 KB |
Output is correct |
7 |
Correct |
2 ms |
9052 KB |
Output is correct |
8 |
Correct |
3 ms |
9048 KB |
Output is correct |
9 |
Correct |
3 ms |
11384 KB |
Output is correct |
10 |
Correct |
3 ms |
11356 KB |
Output is correct |
11 |
Correct |
3 ms |
11368 KB |
Output is correct |
12 |
Correct |
3 ms |
11356 KB |
Output is correct |
13 |
Correct |
3 ms |
11356 KB |
Output is correct |
14 |
Correct |
3 ms |
11356 KB |
Output is correct |
15 |
Correct |
4 ms |
11352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
9048 KB |
Output is correct |
2 |
Correct |
3 ms |
11352 KB |
Output is correct |
3 |
Correct |
3 ms |
11352 KB |
Output is correct |
4 |
Correct |
2 ms |
9052 KB |
Output is correct |
5 |
Correct |
3 ms |
11356 KB |
Output is correct |
6 |
Correct |
3 ms |
11356 KB |
Output is correct |
7 |
Correct |
2 ms |
9052 KB |
Output is correct |
8 |
Correct |
3 ms |
9048 KB |
Output is correct |
9 |
Correct |
3 ms |
11384 KB |
Output is correct |
10 |
Correct |
3 ms |
11356 KB |
Output is correct |
11 |
Correct |
3 ms |
11368 KB |
Output is correct |
12 |
Correct |
3 ms |
11356 KB |
Output is correct |
13 |
Correct |
3 ms |
11356 KB |
Output is correct |
14 |
Correct |
3 ms |
11356 KB |
Output is correct |
15 |
Correct |
4 ms |
11352 KB |
Output is correct |
16 |
Correct |
159 ms |
57276 KB |
Output is correct |
17 |
Correct |
465 ms |
99664 KB |
Output is correct |
18 |
Correct |
32 ms |
21792 KB |
Output is correct |
19 |
Correct |
148 ms |
63952 KB |
Output is correct |
20 |
Correct |
415 ms |
100012 KB |
Output is correct |
21 |
Correct |
254 ms |
73656 KB |
Output is correct |
22 |
Correct |
144 ms |
70940 KB |
Output is correct |
23 |
Correct |
458 ms |
99652 KB |
Output is correct |
24 |
Correct |
413 ms |
99760 KB |
Output is correct |
25 |
Correct |
420 ms |
99760 KB |
Output is correct |
26 |
Correct |
146 ms |
63636 KB |
Output is correct |
27 |
Correct |
148 ms |
64236 KB |
Output is correct |
28 |
Correct |
152 ms |
63632 KB |
Output is correct |
29 |
Correct |
146 ms |
64284 KB |
Output is correct |
30 |
Correct |
147 ms |
64020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
9048 KB |
Output is correct |
2 |
Correct |
2 ms |
9056 KB |
Output is correct |
3 |
Correct |
3 ms |
9056 KB |
Output is correct |
4 |
Correct |
2 ms |
9052 KB |
Output is correct |
5 |
Correct |
2 ms |
9052 KB |
Output is correct |
6 |
Correct |
3 ms |
9052 KB |
Output is correct |
7 |
Correct |
2 ms |
9052 KB |
Output is correct |
8 |
Correct |
2 ms |
9052 KB |
Output is correct |
9 |
Correct |
2 ms |
9048 KB |
Output is correct |
10 |
Correct |
2 ms |
9052 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
247 ms |
70888 KB |
Output is correct |
2 |
Correct |
405 ms |
97628 KB |
Output is correct |
3 |
Correct |
405 ms |
98144 KB |
Output is correct |
4 |
Correct |
113 ms |
66160 KB |
Output is correct |
5 |
Correct |
424 ms |
97908 KB |
Output is correct |
6 |
Correct |
362 ms |
98124 KB |
Output is correct |
7 |
Correct |
438 ms |
97948 KB |
Output is correct |
8 |
Correct |
374 ms |
98476 KB |
Output is correct |
9 |
Correct |
351 ms |
97964 KB |
Output is correct |
10 |
Correct |
379 ms |
98228 KB |
Output is correct |
11 |
Correct |
332 ms |
97960 KB |
Output is correct |
12 |
Correct |
423 ms |
98072 KB |
Output is correct |
13 |
Correct |
365 ms |
97928 KB |
Output is correct |
14 |
Correct |
416 ms |
98036 KB |
Output is correct |
15 |
Correct |
392 ms |
101544 KB |
Output is correct |
16 |
Correct |
364 ms |
97956 KB |
Output is correct |
17 |
Correct |
397 ms |
98376 KB |
Output is correct |
18 |
Correct |
387 ms |
98000 KB |
Output is correct |
19 |
Correct |
125 ms |
68844 KB |
Output is correct |
20 |
Correct |
373 ms |
98204 KB |
Output is correct |
21 |
Correct |
409 ms |
98420 KB |
Output is correct |
22 |
Correct |
119 ms |
62900 KB |
Output is correct |
23 |
Correct |
114 ms |
64300 KB |
Output is correct |
24 |
Correct |
107 ms |
62816 KB |
Output is correct |
25 |
Correct |
108 ms |
62368 KB |
Output is correct |
26 |
Correct |
127 ms |
63468 KB |
Output is correct |
27 |
Correct |
152 ms |
67904 KB |
Output is correct |
28 |
Correct |
100 ms |
62316 KB |
Output is correct |
29 |
Correct |
105 ms |
67436 KB |
Output is correct |
30 |
Correct |
96 ms |
62296 KB |
Output is correct |
31 |
Correct |
100 ms |
66960 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
9048 KB |
Output is correct |
2 |
Correct |
3 ms |
11352 KB |
Output is correct |
3 |
Correct |
3 ms |
11352 KB |
Output is correct |
4 |
Correct |
2 ms |
9052 KB |
Output is correct |
5 |
Correct |
3 ms |
11356 KB |
Output is correct |
6 |
Correct |
3 ms |
11356 KB |
Output is correct |
7 |
Correct |
2 ms |
9052 KB |
Output is correct |
8 |
Correct |
3 ms |
9048 KB |
Output is correct |
9 |
Correct |
3 ms |
11384 KB |
Output is correct |
10 |
Correct |
3 ms |
11356 KB |
Output is correct |
11 |
Correct |
3 ms |
11368 KB |
Output is correct |
12 |
Correct |
3 ms |
11356 KB |
Output is correct |
13 |
Correct |
3 ms |
11356 KB |
Output is correct |
14 |
Correct |
3 ms |
11356 KB |
Output is correct |
15 |
Correct |
4 ms |
11352 KB |
Output is correct |
16 |
Correct |
159 ms |
57276 KB |
Output is correct |
17 |
Correct |
465 ms |
99664 KB |
Output is correct |
18 |
Correct |
32 ms |
21792 KB |
Output is correct |
19 |
Correct |
148 ms |
63952 KB |
Output is correct |
20 |
Correct |
415 ms |
100012 KB |
Output is correct |
21 |
Correct |
254 ms |
73656 KB |
Output is correct |
22 |
Correct |
144 ms |
70940 KB |
Output is correct |
23 |
Correct |
458 ms |
99652 KB |
Output is correct |
24 |
Correct |
413 ms |
99760 KB |
Output is correct |
25 |
Correct |
420 ms |
99760 KB |
Output is correct |
26 |
Correct |
146 ms |
63636 KB |
Output is correct |
27 |
Correct |
148 ms |
64236 KB |
Output is correct |
28 |
Correct |
152 ms |
63632 KB |
Output is correct |
29 |
Correct |
146 ms |
64284 KB |
Output is correct |
30 |
Correct |
147 ms |
64020 KB |
Output is correct |
31 |
Correct |
2 ms |
9048 KB |
Output is correct |
32 |
Correct |
2 ms |
9056 KB |
Output is correct |
33 |
Correct |
3 ms |
9056 KB |
Output is correct |
34 |
Correct |
2 ms |
9052 KB |
Output is correct |
35 |
Correct |
2 ms |
9052 KB |
Output is correct |
36 |
Correct |
3 ms |
9052 KB |
Output is correct |
37 |
Correct |
2 ms |
9052 KB |
Output is correct |
38 |
Correct |
2 ms |
9052 KB |
Output is correct |
39 |
Correct |
2 ms |
9048 KB |
Output is correct |
40 |
Correct |
2 ms |
9052 KB |
Output is correct |
41 |
Correct |
247 ms |
70888 KB |
Output is correct |
42 |
Correct |
405 ms |
97628 KB |
Output is correct |
43 |
Correct |
405 ms |
98144 KB |
Output is correct |
44 |
Correct |
113 ms |
66160 KB |
Output is correct |
45 |
Correct |
424 ms |
97908 KB |
Output is correct |
46 |
Correct |
362 ms |
98124 KB |
Output is correct |
47 |
Correct |
438 ms |
97948 KB |
Output is correct |
48 |
Correct |
374 ms |
98476 KB |
Output is correct |
49 |
Correct |
351 ms |
97964 KB |
Output is correct |
50 |
Correct |
379 ms |
98228 KB |
Output is correct |
51 |
Correct |
332 ms |
97960 KB |
Output is correct |
52 |
Correct |
423 ms |
98072 KB |
Output is correct |
53 |
Correct |
365 ms |
97928 KB |
Output is correct |
54 |
Correct |
416 ms |
98036 KB |
Output is correct |
55 |
Correct |
392 ms |
101544 KB |
Output is correct |
56 |
Correct |
364 ms |
97956 KB |
Output is correct |
57 |
Correct |
397 ms |
98376 KB |
Output is correct |
58 |
Correct |
387 ms |
98000 KB |
Output is correct |
59 |
Correct |
125 ms |
68844 KB |
Output is correct |
60 |
Correct |
373 ms |
98204 KB |
Output is correct |
61 |
Correct |
409 ms |
98420 KB |
Output is correct |
62 |
Correct |
119 ms |
62900 KB |
Output is correct |
63 |
Correct |
114 ms |
64300 KB |
Output is correct |
64 |
Correct |
107 ms |
62816 KB |
Output is correct |
65 |
Correct |
108 ms |
62368 KB |
Output is correct |
66 |
Correct |
127 ms |
63468 KB |
Output is correct |
67 |
Correct |
152 ms |
67904 KB |
Output is correct |
68 |
Correct |
100 ms |
62316 KB |
Output is correct |
69 |
Correct |
105 ms |
67436 KB |
Output is correct |
70 |
Correct |
96 ms |
62296 KB |
Output is correct |
71 |
Correct |
100 ms |
66960 KB |
Output is correct |
72 |
Correct |
288 ms |
73256 KB |
Output is correct |
73 |
Correct |
442 ms |
100308 KB |
Output is correct |
74 |
Correct |
460 ms |
100148 KB |
Output is correct |
75 |
Correct |
553 ms |
99644 KB |
Output is correct |
76 |
Correct |
582 ms |
99816 KB |
Output is correct |
77 |
Correct |
538 ms |
99960 KB |
Output is correct |
78 |
Correct |
445 ms |
99944 KB |
Output is correct |
79 |
Correct |
537 ms |
99748 KB |
Output is correct |
80 |
Correct |
509 ms |
100180 KB |
Output is correct |
81 |
Correct |
551 ms |
99632 KB |
Output is correct |
82 |
Correct |
510 ms |
99784 KB |
Output is correct |
83 |
Correct |
457 ms |
99724 KB |
Output is correct |
84 |
Correct |
454 ms |
99820 KB |
Output is correct |
85 |
Correct |
381 ms |
103072 KB |
Output is correct |
86 |
Correct |
372 ms |
99656 KB |
Output is correct |
87 |
Correct |
412 ms |
99572 KB |
Output is correct |
88 |
Correct |
500 ms |
99788 KB |
Output is correct |
89 |
Correct |
265 ms |
69232 KB |
Output is correct |
90 |
Correct |
477 ms |
99688 KB |
Output is correct |
91 |
Correct |
409 ms |
99968 KB |
Output is correct |
92 |
Correct |
159 ms |
63700 KB |
Output is correct |
93 |
Correct |
223 ms |
65688 KB |
Output is correct |
94 |
Correct |
162 ms |
63836 KB |
Output is correct |
95 |
Correct |
175 ms |
64304 KB |
Output is correct |
96 |
Correct |
234 ms |
65216 KB |
Output is correct |
97 |
Correct |
294 ms |
68028 KB |
Output is correct |
98 |
Correct |
170 ms |
64172 KB |
Output is correct |
99 |
Correct |
240 ms |
69816 KB |
Output is correct |
100 |
Correct |
192 ms |
63804 KB |
Output is correct |