#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 100000
#define INF 0x3f3f3f3f
int *ej[N], *ew[N], eo[N];
void append(int i, int j, int w) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0) {
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ew[i] = (int *) realloc(ew[i], o * 2 * sizeof *ew[i]);
}
ej[i][o] = j, ew[i][o] = w;
}
int dd[N], iq[N + 1], pq[N], cnt;
int lt(int i, int j) { return dd[i] < dd[j]; }
int p2(int p) {
return (p *= 2) > cnt ? 0 : (p < cnt && lt(iq[p + 1], iq[p]) ? p + 1 : p);
}
void pq_up(int i) {
int p, q, j;
for (p = pq[i]; (q = p / 2) && lt(i, j = iq[q]); p = q)
iq[pq[j] = p] = j;
iq[pq[i] = p] = i;
}
void pq_dn(int i) {
int p, q, j;
for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
iq[pq[j] = p] = j;
iq[pq[i] = p] = i;
}
void pq_add_last(int i) {
iq[pq[i] = ++cnt] = i;
}
int pq_remove_first() {
int i = iq[1], j = iq[cnt--];
if (j != i)
pq[j] = 1, pq_dn(j);
pq[i] = 0;
return i;
}
int ds[N], ww[N];
int find(int i) {
return ds[i] < 0 ? i : find(ds[i]);
}
void join(int i, int j, int w) {
i = find(i);
j = find(j);
if (i == j)
return;
if (ds[i] > ds[j])
ds[i] = j, ww[i] = w;
else {
if (ds[i] == ds[j])
ds[i]--;
ds[j] = i, ww[j] = w;
}
}
int query(int i, int j) {
int w = INF;
while (i != j)
if (ww[i] > ww[j])
w = ww[i], i = ds[i];
else
w = ww[j], j = ds[j];
return w;
}
int main() {
static int ii[N];
static char active[N];
int n, m, k, q, h, i, j, w, o;
scanf("%d%d", &n, &m);
for (i = 0; i < n; i++) {
ej[i] = (int *) malloc(2 * sizeof *ej[i]);
ew[i] = (int *) malloc(2 * sizeof *ew[i]);
}
while (m--) {
scanf("%d%d%d", &i, &j, &w), i--, j--;
append(i, j, w), append(j, i, w);
}
scanf("%d", &k);
memset(dd, 0x3f, n * sizeof *dd);
while (k--) {
scanf("%d", &i), i--;
dd[i] = 0, pq_add_last(i);
}
for (h = 0; h < n; h++) {
ii[h] = i = pq_remove_first();
for (o = eo[i]; o--; ) {
int d;
j = ej[i][o], w = ew[i][o], d = dd[i] + w;
if (dd[j] > d) {
if (dd[j] == INF)
pq_add_last(j);
dd[j] = d, pq_up(j);
}
}
}
memset(ds, -1, n * sizeof *ds), memset(ww, -1, n * sizeof *ww);
for (h = n - 1; h >= 0; h--) {
i = ii[h];
active[i] = 1;
for (o = eo[i]; o--; ) {
j = ej[i][o];
if (active[j])
join(i, j, dd[i]);
}
}
scanf("%d", &q);
while (q--) {
scanf("%d%d", &i, &j), i--, j--;
printf("%d\n", query(i, j));
}
return 0;
}
Compilation message
plan.c: In function 'append':
plan.c:13:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
13 | if (o >= 2 && (o & o - 1) == 0) {
| ~~^~~
plan.c: In function 'main':
plan.c:93:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
93 | scanf("%d%d", &n, &m);
| ^~~~~~~~~~~~~~~~~~~~~
plan.c:99:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
99 | scanf("%d%d%d", &i, &j, &w), i--, j--;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
plan.c:102:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
102 | scanf("%d", &k);
| ^~~~~~~~~~~~~~~
plan.c:105:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
105 | scanf("%d", &i), i--;
| ^~~~~~~~~~~~~~~
plan.c:131:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
131 | scanf("%d", &q);
| ^~~~~~~~~~~~~~~
plan.c:133:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
133 | scanf("%d%d", &i, &j), i--, j--;
| ^~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
432 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
292 KB |
Output is correct |
9 |
Correct |
1 ms |
432 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
468 KB |
Output is correct |
12 |
Correct |
1 ms |
436 KB |
Output is correct |
13 |
Correct |
1 ms |
468 KB |
Output is correct |
14 |
Correct |
1 ms |
468 KB |
Output is correct |
15 |
Correct |
1 ms |
436 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
432 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
292 KB |
Output is correct |
9 |
Correct |
1 ms |
432 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
468 KB |
Output is correct |
12 |
Correct |
1 ms |
436 KB |
Output is correct |
13 |
Correct |
1 ms |
468 KB |
Output is correct |
14 |
Correct |
1 ms |
468 KB |
Output is correct |
15 |
Correct |
1 ms |
436 KB |
Output is correct |
16 |
Correct |
81 ms |
12140 KB |
Output is correct |
17 |
Correct |
268 ms |
30264 KB |
Output is correct |
18 |
Correct |
18 ms |
2996 KB |
Output is correct |
19 |
Correct |
80 ms |
15072 KB |
Output is correct |
20 |
Correct |
246 ms |
30284 KB |
Output is correct |
21 |
Correct |
133 ms |
17612 KB |
Output is correct |
22 |
Correct |
75 ms |
14272 KB |
Output is correct |
23 |
Correct |
279 ms |
30268 KB |
Output is correct |
24 |
Correct |
258 ms |
30212 KB |
Output is correct |
25 |
Correct |
264 ms |
30188 KB |
Output is correct |
26 |
Correct |
77 ms |
14944 KB |
Output is correct |
27 |
Correct |
83 ms |
14964 KB |
Output is correct |
28 |
Correct |
78 ms |
14944 KB |
Output is correct |
29 |
Correct |
77 ms |
14948 KB |
Output is correct |
30 |
Correct |
85 ms |
15076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
296 KB |
Output is correct |
6 |
Correct |
0 ms |
296 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
96 ms |
15688 KB |
Output is correct |
2 |
Correct |
236 ms |
28632 KB |
Output is correct |
3 |
Correct |
219 ms |
28620 KB |
Output is correct |
4 |
Correct |
36 ms |
12108 KB |
Output is correct |
5 |
Correct |
215 ms |
28576 KB |
Output is correct |
6 |
Correct |
229 ms |
28668 KB |
Output is correct |
7 |
Correct |
230 ms |
28644 KB |
Output is correct |
8 |
Correct |
230 ms |
28616 KB |
Output is correct |
9 |
Correct |
225 ms |
28604 KB |
Output is correct |
10 |
Correct |
247 ms |
28648 KB |
Output is correct |
11 |
Correct |
234 ms |
28732 KB |
Output is correct |
12 |
Correct |
277 ms |
28580 KB |
Output is correct |
13 |
Correct |
241 ms |
28568 KB |
Output is correct |
14 |
Correct |
235 ms |
28664 KB |
Output is correct |
15 |
Correct |
222 ms |
28664 KB |
Output is correct |
16 |
Correct |
254 ms |
28576 KB |
Output is correct |
17 |
Correct |
221 ms |
28588 KB |
Output is correct |
18 |
Correct |
302 ms |
28740 KB |
Output is correct |
19 |
Correct |
38 ms |
12068 KB |
Output is correct |
20 |
Correct |
218 ms |
28628 KB |
Output is correct |
21 |
Correct |
210 ms |
29100 KB |
Output is correct |
22 |
Correct |
69 ms |
13448 KB |
Output is correct |
23 |
Correct |
47 ms |
12492 KB |
Output is correct |
24 |
Correct |
56 ms |
13500 KB |
Output is correct |
25 |
Correct |
54 ms |
13512 KB |
Output is correct |
26 |
Correct |
54 ms |
12460 KB |
Output is correct |
27 |
Correct |
46 ms |
12076 KB |
Output is correct |
28 |
Correct |
51 ms |
13428 KB |
Output is correct |
29 |
Correct |
45 ms |
12184 KB |
Output is correct |
30 |
Correct |
52 ms |
13408 KB |
Output is correct |
31 |
Correct |
37 ms |
12088 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
432 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
292 KB |
Output is correct |
9 |
Correct |
1 ms |
432 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
468 KB |
Output is correct |
12 |
Correct |
1 ms |
436 KB |
Output is correct |
13 |
Correct |
1 ms |
468 KB |
Output is correct |
14 |
Correct |
1 ms |
468 KB |
Output is correct |
15 |
Correct |
1 ms |
436 KB |
Output is correct |
16 |
Correct |
81 ms |
12140 KB |
Output is correct |
17 |
Correct |
268 ms |
30264 KB |
Output is correct |
18 |
Correct |
18 ms |
2996 KB |
Output is correct |
19 |
Correct |
80 ms |
15072 KB |
Output is correct |
20 |
Correct |
246 ms |
30284 KB |
Output is correct |
21 |
Correct |
133 ms |
17612 KB |
Output is correct |
22 |
Correct |
75 ms |
14272 KB |
Output is correct |
23 |
Correct |
279 ms |
30268 KB |
Output is correct |
24 |
Correct |
258 ms |
30212 KB |
Output is correct |
25 |
Correct |
264 ms |
30188 KB |
Output is correct |
26 |
Correct |
77 ms |
14944 KB |
Output is correct |
27 |
Correct |
83 ms |
14964 KB |
Output is correct |
28 |
Correct |
78 ms |
14944 KB |
Output is correct |
29 |
Correct |
77 ms |
14948 KB |
Output is correct |
30 |
Correct |
85 ms |
15076 KB |
Output is correct |
31 |
Correct |
0 ms |
340 KB |
Output is correct |
32 |
Correct |
0 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
340 KB |
Output is correct |
34 |
Correct |
1 ms |
340 KB |
Output is correct |
35 |
Correct |
1 ms |
296 KB |
Output is correct |
36 |
Correct |
0 ms |
296 KB |
Output is correct |
37 |
Correct |
0 ms |
340 KB |
Output is correct |
38 |
Correct |
1 ms |
340 KB |
Output is correct |
39 |
Correct |
0 ms |
340 KB |
Output is correct |
40 |
Correct |
0 ms |
340 KB |
Output is correct |
41 |
Correct |
96 ms |
15688 KB |
Output is correct |
42 |
Correct |
236 ms |
28632 KB |
Output is correct |
43 |
Correct |
219 ms |
28620 KB |
Output is correct |
44 |
Correct |
36 ms |
12108 KB |
Output is correct |
45 |
Correct |
215 ms |
28576 KB |
Output is correct |
46 |
Correct |
229 ms |
28668 KB |
Output is correct |
47 |
Correct |
230 ms |
28644 KB |
Output is correct |
48 |
Correct |
230 ms |
28616 KB |
Output is correct |
49 |
Correct |
225 ms |
28604 KB |
Output is correct |
50 |
Correct |
247 ms |
28648 KB |
Output is correct |
51 |
Correct |
234 ms |
28732 KB |
Output is correct |
52 |
Correct |
277 ms |
28580 KB |
Output is correct |
53 |
Correct |
241 ms |
28568 KB |
Output is correct |
54 |
Correct |
235 ms |
28664 KB |
Output is correct |
55 |
Correct |
222 ms |
28664 KB |
Output is correct |
56 |
Correct |
254 ms |
28576 KB |
Output is correct |
57 |
Correct |
221 ms |
28588 KB |
Output is correct |
58 |
Correct |
302 ms |
28740 KB |
Output is correct |
59 |
Correct |
38 ms |
12068 KB |
Output is correct |
60 |
Correct |
218 ms |
28628 KB |
Output is correct |
61 |
Correct |
210 ms |
29100 KB |
Output is correct |
62 |
Correct |
69 ms |
13448 KB |
Output is correct |
63 |
Correct |
47 ms |
12492 KB |
Output is correct |
64 |
Correct |
56 ms |
13500 KB |
Output is correct |
65 |
Correct |
54 ms |
13512 KB |
Output is correct |
66 |
Correct |
54 ms |
12460 KB |
Output is correct |
67 |
Correct |
46 ms |
12076 KB |
Output is correct |
68 |
Correct |
51 ms |
13428 KB |
Output is correct |
69 |
Correct |
45 ms |
12184 KB |
Output is correct |
70 |
Correct |
52 ms |
13408 KB |
Output is correct |
71 |
Correct |
37 ms |
12088 KB |
Output is correct |
72 |
Correct |
121 ms |
17416 KB |
Output is correct |
73 |
Correct |
259 ms |
30276 KB |
Output is correct |
74 |
Correct |
268 ms |
30412 KB |
Output is correct |
75 |
Correct |
292 ms |
30328 KB |
Output is correct |
76 |
Correct |
286 ms |
30236 KB |
Output is correct |
77 |
Correct |
267 ms |
30308 KB |
Output is correct |
78 |
Correct |
269 ms |
30212 KB |
Output is correct |
79 |
Correct |
278 ms |
30344 KB |
Output is correct |
80 |
Correct |
260 ms |
30192 KB |
Output is correct |
81 |
Correct |
357 ms |
30332 KB |
Output is correct |
82 |
Correct |
276 ms |
30284 KB |
Output is correct |
83 |
Correct |
342 ms |
30236 KB |
Output is correct |
84 |
Correct |
268 ms |
30284 KB |
Output is correct |
85 |
Correct |
263 ms |
30232 KB |
Output is correct |
86 |
Correct |
278 ms |
30256 KB |
Output is correct |
87 |
Correct |
258 ms |
30208 KB |
Output is correct |
88 |
Correct |
261 ms |
30340 KB |
Output is correct |
89 |
Correct |
71 ms |
14220 KB |
Output is correct |
90 |
Correct |
251 ms |
30180 KB |
Output is correct |
91 |
Correct |
242 ms |
30704 KB |
Output is correct |
92 |
Correct |
83 ms |
14944 KB |
Output is correct |
93 |
Correct |
78 ms |
14488 KB |
Output is correct |
94 |
Correct |
76 ms |
14944 KB |
Output is correct |
95 |
Correct |
77 ms |
14976 KB |
Output is correct |
96 |
Correct |
87 ms |
13996 KB |
Output is correct |
97 |
Correct |
62 ms |
13864 KB |
Output is correct |
98 |
Correct |
78 ms |
14960 KB |
Output is correct |
99 |
Correct |
62 ms |
13876 KB |
Output is correct |
100 |
Correct |
106 ms |
15004 KB |
Output is correct |