#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
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
9048 KB |
Output is correct |
2 |
Correct |
3 ms |
11352 KB |
Output is correct |
3 |
Correct |
3 ms |
11368 KB |
Output is correct |
4 |
Correct |
2 ms |
9052 KB |
Output is correct |
5 |
Correct |
3 ms |
11368 KB |
Output is correct |
6 |
Correct |
3 ms |
11352 KB |
Output is correct |
7 |
Correct |
2 ms |
9052 KB |
Output is correct |
8 |
Correct |
2 ms |
8920 KB |
Output is correct |
9 |
Correct |
4 ms |
11356 KB |
Output is correct |
10 |
Correct |
3 ms |
11352 KB |
Output is correct |
11 |
Correct |
3 ms |
11608 KB |
Output is correct |
12 |
Correct |
3 ms |
11352 KB |
Output is correct |
13 |
Correct |
3 ms |
11356 KB |
Output is correct |
14 |
Correct |
3 ms |
11356 KB |
Output is correct |
15 |
Correct |
3 ms |
11356 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
9048 KB |
Output is correct |
2 |
Correct |
3 ms |
11352 KB |
Output is correct |
3 |
Correct |
3 ms |
11368 KB |
Output is correct |
4 |
Correct |
2 ms |
9052 KB |
Output is correct |
5 |
Correct |
3 ms |
11368 KB |
Output is correct |
6 |
Correct |
3 ms |
11352 KB |
Output is correct |
7 |
Correct |
2 ms |
9052 KB |
Output is correct |
8 |
Correct |
2 ms |
8920 KB |
Output is correct |
9 |
Correct |
4 ms |
11356 KB |
Output is correct |
10 |
Correct |
3 ms |
11352 KB |
Output is correct |
11 |
Correct |
3 ms |
11608 KB |
Output is correct |
12 |
Correct |
3 ms |
11352 KB |
Output is correct |
13 |
Correct |
3 ms |
11356 KB |
Output is correct |
14 |
Correct |
3 ms |
11356 KB |
Output is correct |
15 |
Correct |
3 ms |
11356 KB |
Output is correct |
16 |
Correct |
124 ms |
57412 KB |
Output is correct |
17 |
Correct |
342 ms |
99840 KB |
Output is correct |
18 |
Correct |
25 ms |
21956 KB |
Output is correct |
19 |
Correct |
114 ms |
64536 KB |
Output is correct |
20 |
Correct |
323 ms |
99668 KB |
Output is correct |
21 |
Correct |
197 ms |
74528 KB |
Output is correct |
22 |
Correct |
126 ms |
70564 KB |
Output is correct |
23 |
Correct |
343 ms |
100024 KB |
Output is correct |
24 |
Correct |
346 ms |
99656 KB |
Output is correct |
25 |
Correct |
334 ms |
99800 KB |
Output is correct |
26 |
Correct |
113 ms |
63660 KB |
Output is correct |
27 |
Correct |
119 ms |
63708 KB |
Output is correct |
28 |
Correct |
113 ms |
63720 KB |
Output is correct |
29 |
Correct |
122 ms |
64160 KB |
Output is correct |
30 |
Correct |
115 ms |
63828 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
9052 KB |
Output is correct |
2 |
Correct |
2 ms |
9060 KB |
Output is correct |
3 |
Correct |
2 ms |
9052 KB |
Output is correct |
4 |
Correct |
2 ms |
9048 KB |
Output is correct |
5 |
Correct |
2 ms |
9052 KB |
Output is correct |
6 |
Correct |
2 ms |
9052 KB |
Output is correct |
7 |
Correct |
2 ms |
9052 KB |
Output is correct |
8 |
Correct |
2 ms |
9048 KB |
Output is correct |
9 |
Correct |
2 ms |
9052 KB |
Output is correct |
10 |
Correct |
2 ms |
9052 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
196 ms |
68432 KB |
Output is correct |
2 |
Correct |
293 ms |
97896 KB |
Output is correct |
3 |
Correct |
281 ms |
97964 KB |
Output is correct |
4 |
Correct |
91 ms |
66144 KB |
Output is correct |
5 |
Correct |
295 ms |
98560 KB |
Output is correct |
6 |
Correct |
284 ms |
98048 KB |
Output is correct |
7 |
Correct |
290 ms |
97972 KB |
Output is correct |
8 |
Correct |
300 ms |
98152 KB |
Output is correct |
9 |
Correct |
299 ms |
98472 KB |
Output is correct |
10 |
Correct |
288 ms |
98316 KB |
Output is correct |
11 |
Correct |
296 ms |
98524 KB |
Output is correct |
12 |
Correct |
298 ms |
97948 KB |
Output is correct |
13 |
Correct |
289 ms |
97968 KB |
Output is correct |
14 |
Correct |
294 ms |
98268 KB |
Output is correct |
15 |
Correct |
309 ms |
102196 KB |
Output is correct |
16 |
Correct |
288 ms |
98472 KB |
Output is correct |
17 |
Correct |
289 ms |
98340 KB |
Output is correct |
18 |
Correct |
289 ms |
98052 KB |
Output is correct |
19 |
Correct |
90 ms |
68216 KB |
Output is correct |
20 |
Correct |
286 ms |
98540 KB |
Output is correct |
21 |
Correct |
269 ms |
98420 KB |
Output is correct |
22 |
Correct |
93 ms |
62364 KB |
Output is correct |
23 |
Correct |
93 ms |
63896 KB |
Output is correct |
24 |
Correct |
90 ms |
62312 KB |
Output is correct |
25 |
Correct |
88 ms |
62300 KB |
Output is correct |
26 |
Correct |
102 ms |
63680 KB |
Output is correct |
27 |
Correct |
93 ms |
68028 KB |
Output is correct |
28 |
Correct |
82 ms |
62236 KB |
Output is correct |
29 |
Correct |
97 ms |
67004 KB |
Output is correct |
30 |
Correct |
86 ms |
62372 KB |
Output is correct |
31 |
Correct |
103 ms |
67176 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
9048 KB |
Output is correct |
2 |
Correct |
3 ms |
11352 KB |
Output is correct |
3 |
Correct |
3 ms |
11368 KB |
Output is correct |
4 |
Correct |
2 ms |
9052 KB |
Output is correct |
5 |
Correct |
3 ms |
11368 KB |
Output is correct |
6 |
Correct |
3 ms |
11352 KB |
Output is correct |
7 |
Correct |
2 ms |
9052 KB |
Output is correct |
8 |
Correct |
2 ms |
8920 KB |
Output is correct |
9 |
Correct |
4 ms |
11356 KB |
Output is correct |
10 |
Correct |
3 ms |
11352 KB |
Output is correct |
11 |
Correct |
3 ms |
11608 KB |
Output is correct |
12 |
Correct |
3 ms |
11352 KB |
Output is correct |
13 |
Correct |
3 ms |
11356 KB |
Output is correct |
14 |
Correct |
3 ms |
11356 KB |
Output is correct |
15 |
Correct |
3 ms |
11356 KB |
Output is correct |
16 |
Correct |
124 ms |
57412 KB |
Output is correct |
17 |
Correct |
342 ms |
99840 KB |
Output is correct |
18 |
Correct |
25 ms |
21956 KB |
Output is correct |
19 |
Correct |
114 ms |
64536 KB |
Output is correct |
20 |
Correct |
323 ms |
99668 KB |
Output is correct |
21 |
Correct |
197 ms |
74528 KB |
Output is correct |
22 |
Correct |
126 ms |
70564 KB |
Output is correct |
23 |
Correct |
343 ms |
100024 KB |
Output is correct |
24 |
Correct |
346 ms |
99656 KB |
Output is correct |
25 |
Correct |
334 ms |
99800 KB |
Output is correct |
26 |
Correct |
113 ms |
63660 KB |
Output is correct |
27 |
Correct |
119 ms |
63708 KB |
Output is correct |
28 |
Correct |
113 ms |
63720 KB |
Output is correct |
29 |
Correct |
122 ms |
64160 KB |
Output is correct |
30 |
Correct |
115 ms |
63828 KB |
Output is correct |
31 |
Correct |
2 ms |
9052 KB |
Output is correct |
32 |
Correct |
2 ms |
9060 KB |
Output is correct |
33 |
Correct |
2 ms |
9052 KB |
Output is correct |
34 |
Correct |
2 ms |
9048 KB |
Output is correct |
35 |
Correct |
2 ms |
9052 KB |
Output is correct |
36 |
Correct |
2 ms |
9052 KB |
Output is correct |
37 |
Correct |
2 ms |
9052 KB |
Output is correct |
38 |
Correct |
2 ms |
9048 KB |
Output is correct |
39 |
Correct |
2 ms |
9052 KB |
Output is correct |
40 |
Correct |
2 ms |
9052 KB |
Output is correct |
41 |
Correct |
196 ms |
68432 KB |
Output is correct |
42 |
Correct |
293 ms |
97896 KB |
Output is correct |
43 |
Correct |
281 ms |
97964 KB |
Output is correct |
44 |
Correct |
91 ms |
66144 KB |
Output is correct |
45 |
Correct |
295 ms |
98560 KB |
Output is correct |
46 |
Correct |
284 ms |
98048 KB |
Output is correct |
47 |
Correct |
290 ms |
97972 KB |
Output is correct |
48 |
Correct |
300 ms |
98152 KB |
Output is correct |
49 |
Correct |
299 ms |
98472 KB |
Output is correct |
50 |
Correct |
288 ms |
98316 KB |
Output is correct |
51 |
Correct |
296 ms |
98524 KB |
Output is correct |
52 |
Correct |
298 ms |
97948 KB |
Output is correct |
53 |
Correct |
289 ms |
97968 KB |
Output is correct |
54 |
Correct |
294 ms |
98268 KB |
Output is correct |
55 |
Correct |
309 ms |
102196 KB |
Output is correct |
56 |
Correct |
288 ms |
98472 KB |
Output is correct |
57 |
Correct |
289 ms |
98340 KB |
Output is correct |
58 |
Correct |
289 ms |
98052 KB |
Output is correct |
59 |
Correct |
90 ms |
68216 KB |
Output is correct |
60 |
Correct |
286 ms |
98540 KB |
Output is correct |
61 |
Correct |
269 ms |
98420 KB |
Output is correct |
62 |
Correct |
93 ms |
62364 KB |
Output is correct |
63 |
Correct |
93 ms |
63896 KB |
Output is correct |
64 |
Correct |
90 ms |
62312 KB |
Output is correct |
65 |
Correct |
88 ms |
62300 KB |
Output is correct |
66 |
Correct |
102 ms |
63680 KB |
Output is correct |
67 |
Correct |
93 ms |
68028 KB |
Output is correct |
68 |
Correct |
82 ms |
62236 KB |
Output is correct |
69 |
Correct |
97 ms |
67004 KB |
Output is correct |
70 |
Correct |
86 ms |
62372 KB |
Output is correct |
71 |
Correct |
103 ms |
67176 KB |
Output is correct |
72 |
Correct |
268 ms |
73940 KB |
Output is correct |
73 |
Correct |
358 ms |
99796 KB |
Output is correct |
74 |
Correct |
367 ms |
99948 KB |
Output is correct |
75 |
Correct |
356 ms |
100272 KB |
Output is correct |
76 |
Correct |
346 ms |
99828 KB |
Output is correct |
77 |
Correct |
351 ms |
99676 KB |
Output is correct |
78 |
Correct |
361 ms |
99756 KB |
Output is correct |
79 |
Correct |
359 ms |
99644 KB |
Output is correct |
80 |
Correct |
337 ms |
99732 KB |
Output is correct |
81 |
Correct |
374 ms |
99596 KB |
Output is correct |
82 |
Correct |
353 ms |
99636 KB |
Output is correct |
83 |
Correct |
360 ms |
99800 KB |
Output is correct |
84 |
Correct |
354 ms |
100404 KB |
Output is correct |
85 |
Correct |
358 ms |
102964 KB |
Output is correct |
86 |
Correct |
329 ms |
99724 KB |
Output is correct |
87 |
Correct |
341 ms |
99796 KB |
Output is correct |
88 |
Correct |
348 ms |
99696 KB |
Output is correct |
89 |
Correct |
197 ms |
69304 KB |
Output is correct |
90 |
Correct |
374 ms |
99624 KB |
Output is correct |
91 |
Correct |
330 ms |
99988 KB |
Output is correct |
92 |
Correct |
128 ms |
63820 KB |
Output is correct |
93 |
Correct |
168 ms |
66236 KB |
Output is correct |
94 |
Correct |
123 ms |
63664 KB |
Output is correct |
95 |
Correct |
136 ms |
63900 KB |
Output is correct |
96 |
Correct |
186 ms |
65208 KB |
Output is correct |
97 |
Correct |
215 ms |
68028 KB |
Output is correct |
98 |
Correct |
133 ms |
63656 KB |
Output is correct |
99 |
Correct |
214 ms |
70216 KB |
Output is correct |
100 |
Correct |
126 ms |
63812 KB |
Output is correct |