#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 1e5 + 10;
const int MAXLG = 17;
const int INF = 1e8;
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define all(v) (v).begin(), (v).end()
#define fi first
#define se second
#define fillchar(a, s) memset((a), (s), sizeof(a))
int N, M;
vector<pii> adj[MAXN];
struct union_find {
int par[MAXN];
void reset() {
for (int i = 0; i < N; i++) {
par[i] = i;
}
}
int find (int x) {
return x == par[x] ? x : par[x] = find(par[x]);
}
bool merge (int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return false;
}
par[x] = y;
return true;
}
} uf;
int K, G[MAXN];
int dist[MAXN];
bool vis[MAXN];
int Q;
//code for dijkstra
void dijkstra() {
priority_queue<pii, vector<pii>, greater<pii>> pq;
for (int i = 0; i < N; i++) {
dist[i] = INF;
}
for (int i = 0; i < K; i++) {
int x = G[i];
dist[x] = 0;
pq.push({0, x});
}
while (!pq.empty()) {
int u = pq.top().se, w = pq.top().fi;
pq.pop();
if (vis[u]) {
continue;
}
vis[u] = true;
for (pii e : adj[u]) {
int v = e.se;
int nw = e.fi + w;
if (dist[v] > nw) {
dist[v] = nw;
pq.push({nw, v});
}
}
}
/*
for (int i = 0; i < N; i++) {
debug("dist[%d] = %d\n", i, dist[i]);
}
*/
}
vector<pii> tree[MAXN];
int par[MAXN][MAXLG];
int mnw[MAXN][MAXLG];
int depth[MAXN];
void dfs (int x) {
for (pii e : tree[x]) {
int w = e.fi;
int y = e.se;
for (auto it = tree[y].begin(); ; it++) {
if (it->se == x) {
tree[y].erase(it);
break;
}
}
depth[y] = depth[x] + 1;
par[y][0] = x;
mnw[y][0] = w;
for (int i = 1; i < MAXLG; i++) {
int pp = par[par[y][i - 1]][i - 1];
if (pp == -1) {
break;
}
par[y][i] = pp;
mnw[y][i] = min(mnw[y][i - 1], mnw[par[y][i - 1]][i - 1]);
}
dfs(y);
}
}
int getpar (int x, int d) {
for (int i = 0; d; i++, d >>= 1) {
if (d & 1) {
x = par[x][i];
}
}
return x;
}
int lca (int x, int y) {
if (depth[x] < depth[y]) {
swap(x, y);
}
x = getpar(x, depth[x] - depth[y]);
if (x == y) {
return x;
}
for (int i = MAXLG - 1; i >= 0; i--) {
if (par[x][i] != par[y][i]) {
x = par[x][i];
y = par[y][i];
}
}
return par[x][0];
}
int minjump (int x, int d) {
if (d == 0) {
return INT_MAX;
}
int res = INT_MAX;
for (int i = 0; d; i++, d >>= 1) {
if (d & 1) {
res = min(res, mnw[x][i]);
x = par[x][i];
}
}
return res;
}
int getmin (int x, int y) {
int c = lca(x, y);
return min(minjump(x, depth[x] - depth[c]), minjump(y, depth[y] - depth[c]));
}
int main() {
scanf("%d %d", &N, &M);
for (int i = 0; i < M; i++) {
int a, b, w;
scanf("%d %d %d", &a, &b, &w);
a--;
b--;
adj[a].push_back({w, b});
adj[b].push_back({w, a});
}
scanf("%d", &K);
for (int i = 0; i < K; i++) {
scanf("%d", &G[i]);
G[i]--;
}
dijkstra();
vector<array<int, 3>> edges;
for (int i = 0; i < N; i++) {
for (pii e : adj[i]) {
int j = e.se;
//min bottleneck path
if (i < j) {
edges.push_back({min(dist[i], dist[j]), i, j});
}
}
}
sort(edges.rbegin(), edges.rend());
uf.reset();
for (auto e : edges) {
if (uf.merge(e[1], e[2])) {
//debug("TREE EDGE %d %d %d\n", e[1], e[2], e[0]);
tree[e[1]].push_back({e[0], e[2]});
tree[e[2]].push_back({e[0], e[1]});
}
}
fillchar(par, -1);
dfs(0);
scanf("%d", &Q);
for (int i = 0; i < Q; i++) {
int s, t;
scanf("%d %d", &s, &t);
printf("%d\n", getmin(s - 1, t - 1));
}
}
Compilation message
plan.cpp: In function 'int main()':
plan.cpp:168:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &N, &M);
~~~~~^~~~~~~~~~~~~~~~~
plan.cpp:171:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &a, &b, &w);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:178:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &K);
~~~~~^~~~~~~~~~
plan.cpp:180:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &G[i]);
~~~~~^~~~~~~~~~~~~
plan.cpp:209:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &Q);
~~~~~^~~~~~~~~~
plan.cpp:212:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &s, &t);
~~~~~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
11640 KB |
Output is correct |
2 |
Correct |
13 ms |
11896 KB |
Output is correct |
3 |
Correct |
12 ms |
11868 KB |
Output is correct |
4 |
Correct |
12 ms |
11768 KB |
Output is correct |
5 |
Correct |
12 ms |
11896 KB |
Output is correct |
6 |
Correct |
12 ms |
11896 KB |
Output is correct |
7 |
Correct |
11 ms |
11640 KB |
Output is correct |
8 |
Correct |
12 ms |
11640 KB |
Output is correct |
9 |
Correct |
13 ms |
11896 KB |
Output is correct |
10 |
Correct |
13 ms |
11896 KB |
Output is correct |
11 |
Correct |
13 ms |
11896 KB |
Output is correct |
12 |
Correct |
13 ms |
11896 KB |
Output is correct |
13 |
Correct |
13 ms |
11896 KB |
Output is correct |
14 |
Correct |
13 ms |
11896 KB |
Output is correct |
15 |
Correct |
13 ms |
11896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
11640 KB |
Output is correct |
2 |
Correct |
13 ms |
11896 KB |
Output is correct |
3 |
Correct |
12 ms |
11868 KB |
Output is correct |
4 |
Correct |
12 ms |
11768 KB |
Output is correct |
5 |
Correct |
12 ms |
11896 KB |
Output is correct |
6 |
Correct |
12 ms |
11896 KB |
Output is correct |
7 |
Correct |
11 ms |
11640 KB |
Output is correct |
8 |
Correct |
12 ms |
11640 KB |
Output is correct |
9 |
Correct |
13 ms |
11896 KB |
Output is correct |
10 |
Correct |
13 ms |
11896 KB |
Output is correct |
11 |
Correct |
13 ms |
11896 KB |
Output is correct |
12 |
Correct |
13 ms |
11896 KB |
Output is correct |
13 |
Correct |
13 ms |
11896 KB |
Output is correct |
14 |
Correct |
13 ms |
11896 KB |
Output is correct |
15 |
Correct |
13 ms |
11896 KB |
Output is correct |
16 |
Correct |
217 ms |
25664 KB |
Output is correct |
17 |
Correct |
711 ms |
42308 KB |
Output is correct |
18 |
Correct |
57 ms |
14728 KB |
Output is correct |
19 |
Correct |
172 ms |
29016 KB |
Output is correct |
20 |
Correct |
711 ms |
42464 KB |
Output is correct |
21 |
Correct |
348 ms |
31860 KB |
Output is correct |
22 |
Correct |
232 ms |
32516 KB |
Output is correct |
23 |
Correct |
709 ms |
42456 KB |
Output is correct |
24 |
Correct |
710 ms |
42208 KB |
Output is correct |
25 |
Correct |
753 ms |
42184 KB |
Output is correct |
26 |
Correct |
175 ms |
28760 KB |
Output is correct |
27 |
Correct |
179 ms |
28884 KB |
Output is correct |
28 |
Correct |
182 ms |
28968 KB |
Output is correct |
29 |
Correct |
178 ms |
28964 KB |
Output is correct |
30 |
Correct |
177 ms |
29020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
11768 KB |
Output is correct |
2 |
Correct |
12 ms |
11640 KB |
Output is correct |
3 |
Correct |
12 ms |
11768 KB |
Output is correct |
4 |
Correct |
12 ms |
11740 KB |
Output is correct |
5 |
Correct |
12 ms |
11768 KB |
Output is correct |
6 |
Correct |
12 ms |
11640 KB |
Output is correct |
7 |
Correct |
12 ms |
11640 KB |
Output is correct |
8 |
Correct |
12 ms |
11640 KB |
Output is correct |
9 |
Correct |
12 ms |
11768 KB |
Output is correct |
10 |
Correct |
11 ms |
11640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
292 ms |
31392 KB |
Output is correct |
2 |
Correct |
630 ms |
41740 KB |
Output is correct |
3 |
Correct |
624 ms |
41844 KB |
Output is correct |
4 |
Correct |
162 ms |
29896 KB |
Output is correct |
5 |
Correct |
639 ms |
41708 KB |
Output is correct |
6 |
Correct |
641 ms |
41732 KB |
Output is correct |
7 |
Correct |
653 ms |
41828 KB |
Output is correct |
8 |
Correct |
629 ms |
41924 KB |
Output is correct |
9 |
Correct |
648 ms |
41720 KB |
Output is correct |
10 |
Correct |
651 ms |
41768 KB |
Output is correct |
11 |
Correct |
674 ms |
41840 KB |
Output is correct |
12 |
Correct |
651 ms |
41720 KB |
Output is correct |
13 |
Correct |
656 ms |
41712 KB |
Output is correct |
14 |
Correct |
662 ms |
41996 KB |
Output is correct |
15 |
Correct |
674 ms |
42672 KB |
Output is correct |
16 |
Correct |
677 ms |
41952 KB |
Output is correct |
17 |
Correct |
634 ms |
41872 KB |
Output is correct |
18 |
Correct |
634 ms |
41716 KB |
Output is correct |
19 |
Correct |
172 ms |
31428 KB |
Output is correct |
20 |
Correct |
639 ms |
41912 KB |
Output is correct |
21 |
Correct |
607 ms |
42088 KB |
Output is correct |
22 |
Correct |
129 ms |
28820 KB |
Output is correct |
23 |
Correct |
168 ms |
28880 KB |
Output is correct |
24 |
Correct |
133 ms |
29080 KB |
Output is correct |
25 |
Correct |
135 ms |
28968 KB |
Output is correct |
26 |
Correct |
179 ms |
29280 KB |
Output is correct |
27 |
Correct |
177 ms |
31644 KB |
Output is correct |
28 |
Correct |
129 ms |
29124 KB |
Output is correct |
29 |
Correct |
171 ms |
30988 KB |
Output is correct |
30 |
Correct |
123 ms |
28988 KB |
Output is correct |
31 |
Correct |
172 ms |
30956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
11640 KB |
Output is correct |
2 |
Correct |
13 ms |
11896 KB |
Output is correct |
3 |
Correct |
12 ms |
11868 KB |
Output is correct |
4 |
Correct |
12 ms |
11768 KB |
Output is correct |
5 |
Correct |
12 ms |
11896 KB |
Output is correct |
6 |
Correct |
12 ms |
11896 KB |
Output is correct |
7 |
Correct |
11 ms |
11640 KB |
Output is correct |
8 |
Correct |
12 ms |
11640 KB |
Output is correct |
9 |
Correct |
13 ms |
11896 KB |
Output is correct |
10 |
Correct |
13 ms |
11896 KB |
Output is correct |
11 |
Correct |
13 ms |
11896 KB |
Output is correct |
12 |
Correct |
13 ms |
11896 KB |
Output is correct |
13 |
Correct |
13 ms |
11896 KB |
Output is correct |
14 |
Correct |
13 ms |
11896 KB |
Output is correct |
15 |
Correct |
13 ms |
11896 KB |
Output is correct |
16 |
Correct |
217 ms |
25664 KB |
Output is correct |
17 |
Correct |
711 ms |
42308 KB |
Output is correct |
18 |
Correct |
57 ms |
14728 KB |
Output is correct |
19 |
Correct |
172 ms |
29016 KB |
Output is correct |
20 |
Correct |
711 ms |
42464 KB |
Output is correct |
21 |
Correct |
348 ms |
31860 KB |
Output is correct |
22 |
Correct |
232 ms |
32516 KB |
Output is correct |
23 |
Correct |
709 ms |
42456 KB |
Output is correct |
24 |
Correct |
710 ms |
42208 KB |
Output is correct |
25 |
Correct |
753 ms |
42184 KB |
Output is correct |
26 |
Correct |
175 ms |
28760 KB |
Output is correct |
27 |
Correct |
179 ms |
28884 KB |
Output is correct |
28 |
Correct |
182 ms |
28968 KB |
Output is correct |
29 |
Correct |
178 ms |
28964 KB |
Output is correct |
30 |
Correct |
177 ms |
29020 KB |
Output is correct |
31 |
Correct |
12 ms |
11768 KB |
Output is correct |
32 |
Correct |
12 ms |
11640 KB |
Output is correct |
33 |
Correct |
12 ms |
11768 KB |
Output is correct |
34 |
Correct |
12 ms |
11740 KB |
Output is correct |
35 |
Correct |
12 ms |
11768 KB |
Output is correct |
36 |
Correct |
12 ms |
11640 KB |
Output is correct |
37 |
Correct |
12 ms |
11640 KB |
Output is correct |
38 |
Correct |
12 ms |
11640 KB |
Output is correct |
39 |
Correct |
12 ms |
11768 KB |
Output is correct |
40 |
Correct |
11 ms |
11640 KB |
Output is correct |
41 |
Correct |
292 ms |
31392 KB |
Output is correct |
42 |
Correct |
630 ms |
41740 KB |
Output is correct |
43 |
Correct |
624 ms |
41844 KB |
Output is correct |
44 |
Correct |
162 ms |
29896 KB |
Output is correct |
45 |
Correct |
639 ms |
41708 KB |
Output is correct |
46 |
Correct |
641 ms |
41732 KB |
Output is correct |
47 |
Correct |
653 ms |
41828 KB |
Output is correct |
48 |
Correct |
629 ms |
41924 KB |
Output is correct |
49 |
Correct |
648 ms |
41720 KB |
Output is correct |
50 |
Correct |
651 ms |
41768 KB |
Output is correct |
51 |
Correct |
674 ms |
41840 KB |
Output is correct |
52 |
Correct |
651 ms |
41720 KB |
Output is correct |
53 |
Correct |
656 ms |
41712 KB |
Output is correct |
54 |
Correct |
662 ms |
41996 KB |
Output is correct |
55 |
Correct |
674 ms |
42672 KB |
Output is correct |
56 |
Correct |
677 ms |
41952 KB |
Output is correct |
57 |
Correct |
634 ms |
41872 KB |
Output is correct |
58 |
Correct |
634 ms |
41716 KB |
Output is correct |
59 |
Correct |
172 ms |
31428 KB |
Output is correct |
60 |
Correct |
639 ms |
41912 KB |
Output is correct |
61 |
Correct |
607 ms |
42088 KB |
Output is correct |
62 |
Correct |
129 ms |
28820 KB |
Output is correct |
63 |
Correct |
168 ms |
28880 KB |
Output is correct |
64 |
Correct |
133 ms |
29080 KB |
Output is correct |
65 |
Correct |
135 ms |
28968 KB |
Output is correct |
66 |
Correct |
179 ms |
29280 KB |
Output is correct |
67 |
Correct |
177 ms |
31644 KB |
Output is correct |
68 |
Correct |
129 ms |
29124 KB |
Output is correct |
69 |
Correct |
171 ms |
30988 KB |
Output is correct |
70 |
Correct |
123 ms |
28988 KB |
Output is correct |
71 |
Correct |
172 ms |
30956 KB |
Output is correct |
72 |
Correct |
413 ms |
32516 KB |
Output is correct |
73 |
Correct |
715 ms |
43120 KB |
Output is correct |
74 |
Correct |
710 ms |
42844 KB |
Output is correct |
75 |
Correct |
724 ms |
43128 KB |
Output is correct |
76 |
Correct |
708 ms |
43132 KB |
Output is correct |
77 |
Correct |
723 ms |
43164 KB |
Output is correct |
78 |
Correct |
786 ms |
42968 KB |
Output is correct |
79 |
Correct |
720 ms |
43096 KB |
Output is correct |
80 |
Correct |
726 ms |
43096 KB |
Output is correct |
81 |
Correct |
740 ms |
43172 KB |
Output is correct |
82 |
Correct |
720 ms |
43004 KB |
Output is correct |
83 |
Correct |
700 ms |
43080 KB |
Output is correct |
84 |
Correct |
779 ms |
43184 KB |
Output is correct |
85 |
Correct |
701 ms |
43912 KB |
Output is correct |
86 |
Correct |
704 ms |
43216 KB |
Output is correct |
87 |
Correct |
726 ms |
43032 KB |
Output is correct |
88 |
Correct |
730 ms |
43164 KB |
Output is correct |
89 |
Correct |
314 ms |
32360 KB |
Output is correct |
90 |
Correct |
744 ms |
43020 KB |
Output is correct |
91 |
Correct |
692 ms |
43244 KB |
Output is correct |
92 |
Correct |
196 ms |
29564 KB |
Output is correct |
93 |
Correct |
282 ms |
30056 KB |
Output is correct |
94 |
Correct |
186 ms |
29400 KB |
Output is correct |
95 |
Correct |
192 ms |
29528 KB |
Output is correct |
96 |
Correct |
291 ms |
29244 KB |
Output is correct |
97 |
Correct |
287 ms |
31080 KB |
Output is correct |
98 |
Correct |
188 ms |
29272 KB |
Output is correct |
99 |
Correct |
297 ms |
32488 KB |
Output is correct |
100 |
Correct |
186 ms |
29388 KB |
Output is correct |