#include <bits/stdc++.h>
using namespace std;
int n, m, q, k;
int par[100010];
int dist[100010];
vector<pair<int, int> > adj[100010];
vector<int> adjTree[100010];
vector<tuple<int, int, int> > edges;
bitset<100010> vis;
priority_queue<pair<int, int> > pq;
const int lgmx = log2(100000) + 2;
int sp[lgmx][100010], cost[lgmx][100010], d[100010];
void init(){
for(int i = 1; i <= n; i++) par[i] = i;
}
int findR(int x){
return par[x] == x ? x : par[x] = findR(par[x]);
}
void join(int a, int b){
par[findR(a)] = findR(b);
}
void dfs(int u, int p){
for(int i = 1; i < lgmx; i++)
if(sp[i - 1][u] != -1) sp[i][u] = sp[i - 1][sp[i - 1][u]], cost[i][u] = min(cost[i - 1][u], cost[i - 1][sp[i - 1][u]]);
for(auto v : adjTree[u]){
if(v == p) continue;
d[v] = d[u] + 1;
sp[0][v] = u;
cost[0][v] = min(dist[u], dist[v]);
dfs(v, u);
}
}
int get(int u, int v){
int c = 1e9;
if(d[u] < d[v]) swap(u, v);
int diff = d[u] - d[v];
for(int i = 0; i < lgmx; i++){
if(diff & (1 << i)) c = min(c, cost[i][u]), u = sp[i][u];
}
if(u == v) return c;
for(int i = lgmx - 1; i >= 0; i--){
if(sp[i][u] != sp[i][v]){
c = min(c, min(cost[i][u], cost[i][v]));
u = sp[i][u], v = sp[i][v];
}
}
return min(c, min(cost[0][u], cost[0][v]));
}
int main(){
scanf("%d%d", &n, &m);
while(m--){
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
for(int i = 1; i <= n; i++) dist[i] = 1e9;
scanf("%d", &k);
while(k--){
int x; scanf("%d", &x);
pq.push({0, x});
dist[x] = 0;
}
//Dijkstra
while(!pq.empty()){
int u, w;
tie(w, u) = pq.top(); pq.pop(); w = -w;
if(vis[u]) continue;
vis[u] = 1;
for(auto k : adj[u]){
int v, w; tie(v, w) = k;
if(dist[v] > dist[u] + w){
dist[v] = dist[u] + w;
pq.push({-dist[v], v});
}
}
}
init();
for(int i = 1; i <= n; i++) pq.push({dist[i], i});
while(!pq.empty()){
int u = pq.top().second; pq.pop();
for(auto k : adj[u]){
int v = k.first;
if(dist[v] >= dist[u] && findR(u) != findR(v)){
join(u, v);
adjTree[u].emplace_back(v);
adjTree[v].emplace_back(u);
}
}
}
for(int i = 1; i <= n; i++)
for(int j = 0; j < lgmx; j++)
cost[j][i] = 1e9;
memset(sp, -1, sizeof(sp));
dfs(1, -1);
scanf("%d", &q);
while(q--){
int u, v;
scanf("%d%d", &u, &v);
printf("%d\n", get(u, v));
}
return 0;
}
Compilation message
plan.cpp: In function 'int main()':
plan.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
plan.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &u, &v, &w);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &k);
~~~~~^~~~~~~~~~
plan.cpp:80:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int x; scanf("%d", &x);
~~~~~^~~~~~~~~~
plan.cpp:126:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
plan.cpp:130:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &u, &v);
~~~~~^~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
12124 KB |
Output is correct |
2 |
Correct |
13 ms |
12380 KB |
Output is correct |
3 |
Correct |
13 ms |
12280 KB |
Output is correct |
4 |
Correct |
12 ms |
12152 KB |
Output is correct |
5 |
Correct |
13 ms |
12420 KB |
Output is correct |
6 |
Correct |
14 ms |
12356 KB |
Output is correct |
7 |
Correct |
12 ms |
12124 KB |
Output is correct |
8 |
Correct |
11 ms |
12156 KB |
Output is correct |
9 |
Correct |
13 ms |
12408 KB |
Output is correct |
10 |
Correct |
13 ms |
12280 KB |
Output is correct |
11 |
Correct |
13 ms |
12284 KB |
Output is correct |
12 |
Correct |
12 ms |
12380 KB |
Output is correct |
13 |
Correct |
14 ms |
12376 KB |
Output is correct |
14 |
Correct |
13 ms |
12380 KB |
Output is correct |
15 |
Correct |
13 ms |
12280 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
12124 KB |
Output is correct |
2 |
Correct |
13 ms |
12380 KB |
Output is correct |
3 |
Correct |
13 ms |
12280 KB |
Output is correct |
4 |
Correct |
12 ms |
12152 KB |
Output is correct |
5 |
Correct |
13 ms |
12420 KB |
Output is correct |
6 |
Correct |
14 ms |
12356 KB |
Output is correct |
7 |
Correct |
12 ms |
12124 KB |
Output is correct |
8 |
Correct |
11 ms |
12156 KB |
Output is correct |
9 |
Correct |
13 ms |
12408 KB |
Output is correct |
10 |
Correct |
13 ms |
12280 KB |
Output is correct |
11 |
Correct |
13 ms |
12284 KB |
Output is correct |
12 |
Correct |
12 ms |
12380 KB |
Output is correct |
13 |
Correct |
14 ms |
12376 KB |
Output is correct |
14 |
Correct |
13 ms |
12380 KB |
Output is correct |
15 |
Correct |
13 ms |
12280 KB |
Output is correct |
16 |
Correct |
243 ms |
26480 KB |
Output is correct |
17 |
Correct |
694 ms |
38580 KB |
Output is correct |
18 |
Correct |
54 ms |
15096 KB |
Output is correct |
19 |
Correct |
215 ms |
29556 KB |
Output is correct |
20 |
Correct |
688 ms |
38588 KB |
Output is correct |
21 |
Correct |
413 ms |
31172 KB |
Output is correct |
22 |
Correct |
266 ms |
33536 KB |
Output is correct |
23 |
Correct |
698 ms |
38520 KB |
Output is correct |
24 |
Correct |
683 ms |
38528 KB |
Output is correct |
25 |
Correct |
695 ms |
38532 KB |
Output is correct |
26 |
Correct |
213 ms |
29380 KB |
Output is correct |
27 |
Correct |
213 ms |
29384 KB |
Output is correct |
28 |
Correct |
211 ms |
29292 KB |
Output is correct |
29 |
Correct |
224 ms |
29520 KB |
Output is correct |
30 |
Correct |
212 ms |
29492 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
12116 KB |
Output is correct |
2 |
Correct |
12 ms |
12152 KB |
Output is correct |
3 |
Correct |
11 ms |
12112 KB |
Output is correct |
4 |
Correct |
12 ms |
12152 KB |
Output is correct |
5 |
Correct |
12 ms |
12152 KB |
Output is correct |
6 |
Correct |
12 ms |
12152 KB |
Output is correct |
7 |
Correct |
12 ms |
12152 KB |
Output is correct |
8 |
Correct |
12 ms |
12136 KB |
Output is correct |
9 |
Correct |
12 ms |
12152 KB |
Output is correct |
10 |
Correct |
12 ms |
12152 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
327 ms |
30864 KB |
Output is correct |
2 |
Correct |
576 ms |
38080 KB |
Output is correct |
3 |
Correct |
597 ms |
38100 KB |
Output is correct |
4 |
Correct |
200 ms |
30804 KB |
Output is correct |
5 |
Correct |
605 ms |
38032 KB |
Output is correct |
6 |
Correct |
652 ms |
38092 KB |
Output is correct |
7 |
Correct |
683 ms |
38132 KB |
Output is correct |
8 |
Correct |
624 ms |
38252 KB |
Output is correct |
9 |
Correct |
617 ms |
37988 KB |
Output is correct |
10 |
Correct |
610 ms |
38056 KB |
Output is correct |
11 |
Correct |
599 ms |
37800 KB |
Output is correct |
12 |
Correct |
607 ms |
38144 KB |
Output is correct |
13 |
Correct |
613 ms |
37948 KB |
Output is correct |
14 |
Correct |
609 ms |
37892 KB |
Output is correct |
15 |
Correct |
617 ms |
38208 KB |
Output is correct |
16 |
Correct |
607 ms |
37948 KB |
Output is correct |
17 |
Correct |
604 ms |
38084 KB |
Output is correct |
18 |
Correct |
607 ms |
38120 KB |
Output is correct |
19 |
Correct |
218 ms |
32272 KB |
Output is correct |
20 |
Correct |
645 ms |
38100 KB |
Output is correct |
21 |
Correct |
640 ms |
37996 KB |
Output is correct |
22 |
Correct |
178 ms |
29028 KB |
Output is correct |
23 |
Correct |
207 ms |
28908 KB |
Output is correct |
24 |
Correct |
167 ms |
29028 KB |
Output is correct |
25 |
Correct |
198 ms |
29060 KB |
Output is correct |
26 |
Correct |
229 ms |
29264 KB |
Output is correct |
27 |
Correct |
215 ms |
32124 KB |
Output is correct |
28 |
Correct |
175 ms |
29044 KB |
Output is correct |
29 |
Correct |
215 ms |
31524 KB |
Output is correct |
30 |
Correct |
173 ms |
29048 KB |
Output is correct |
31 |
Correct |
221 ms |
31512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
12124 KB |
Output is correct |
2 |
Correct |
13 ms |
12380 KB |
Output is correct |
3 |
Correct |
13 ms |
12280 KB |
Output is correct |
4 |
Correct |
12 ms |
12152 KB |
Output is correct |
5 |
Correct |
13 ms |
12420 KB |
Output is correct |
6 |
Correct |
14 ms |
12356 KB |
Output is correct |
7 |
Correct |
12 ms |
12124 KB |
Output is correct |
8 |
Correct |
11 ms |
12156 KB |
Output is correct |
9 |
Correct |
13 ms |
12408 KB |
Output is correct |
10 |
Correct |
13 ms |
12280 KB |
Output is correct |
11 |
Correct |
13 ms |
12284 KB |
Output is correct |
12 |
Correct |
12 ms |
12380 KB |
Output is correct |
13 |
Correct |
14 ms |
12376 KB |
Output is correct |
14 |
Correct |
13 ms |
12380 KB |
Output is correct |
15 |
Correct |
13 ms |
12280 KB |
Output is correct |
16 |
Correct |
243 ms |
26480 KB |
Output is correct |
17 |
Correct |
694 ms |
38580 KB |
Output is correct |
18 |
Correct |
54 ms |
15096 KB |
Output is correct |
19 |
Correct |
215 ms |
29556 KB |
Output is correct |
20 |
Correct |
688 ms |
38588 KB |
Output is correct |
21 |
Correct |
413 ms |
31172 KB |
Output is correct |
22 |
Correct |
266 ms |
33536 KB |
Output is correct |
23 |
Correct |
698 ms |
38520 KB |
Output is correct |
24 |
Correct |
683 ms |
38528 KB |
Output is correct |
25 |
Correct |
695 ms |
38532 KB |
Output is correct |
26 |
Correct |
213 ms |
29380 KB |
Output is correct |
27 |
Correct |
213 ms |
29384 KB |
Output is correct |
28 |
Correct |
211 ms |
29292 KB |
Output is correct |
29 |
Correct |
224 ms |
29520 KB |
Output is correct |
30 |
Correct |
212 ms |
29492 KB |
Output is correct |
31 |
Correct |
12 ms |
12116 KB |
Output is correct |
32 |
Correct |
12 ms |
12152 KB |
Output is correct |
33 |
Correct |
11 ms |
12112 KB |
Output is correct |
34 |
Correct |
12 ms |
12152 KB |
Output is correct |
35 |
Correct |
12 ms |
12152 KB |
Output is correct |
36 |
Correct |
12 ms |
12152 KB |
Output is correct |
37 |
Correct |
12 ms |
12152 KB |
Output is correct |
38 |
Correct |
12 ms |
12136 KB |
Output is correct |
39 |
Correct |
12 ms |
12152 KB |
Output is correct |
40 |
Correct |
12 ms |
12152 KB |
Output is correct |
41 |
Correct |
327 ms |
30864 KB |
Output is correct |
42 |
Correct |
576 ms |
38080 KB |
Output is correct |
43 |
Correct |
597 ms |
38100 KB |
Output is correct |
44 |
Correct |
200 ms |
30804 KB |
Output is correct |
45 |
Correct |
605 ms |
38032 KB |
Output is correct |
46 |
Correct |
652 ms |
38092 KB |
Output is correct |
47 |
Correct |
683 ms |
38132 KB |
Output is correct |
48 |
Correct |
624 ms |
38252 KB |
Output is correct |
49 |
Correct |
617 ms |
37988 KB |
Output is correct |
50 |
Correct |
610 ms |
38056 KB |
Output is correct |
51 |
Correct |
599 ms |
37800 KB |
Output is correct |
52 |
Correct |
607 ms |
38144 KB |
Output is correct |
53 |
Correct |
613 ms |
37948 KB |
Output is correct |
54 |
Correct |
609 ms |
37892 KB |
Output is correct |
55 |
Correct |
617 ms |
38208 KB |
Output is correct |
56 |
Correct |
607 ms |
37948 KB |
Output is correct |
57 |
Correct |
604 ms |
38084 KB |
Output is correct |
58 |
Correct |
607 ms |
38120 KB |
Output is correct |
59 |
Correct |
218 ms |
32272 KB |
Output is correct |
60 |
Correct |
645 ms |
38100 KB |
Output is correct |
61 |
Correct |
640 ms |
37996 KB |
Output is correct |
62 |
Correct |
178 ms |
29028 KB |
Output is correct |
63 |
Correct |
207 ms |
28908 KB |
Output is correct |
64 |
Correct |
167 ms |
29028 KB |
Output is correct |
65 |
Correct |
198 ms |
29060 KB |
Output is correct |
66 |
Correct |
229 ms |
29264 KB |
Output is correct |
67 |
Correct |
215 ms |
32124 KB |
Output is correct |
68 |
Correct |
175 ms |
29044 KB |
Output is correct |
69 |
Correct |
215 ms |
31524 KB |
Output is correct |
70 |
Correct |
173 ms |
29048 KB |
Output is correct |
71 |
Correct |
221 ms |
31512 KB |
Output is correct |
72 |
Correct |
430 ms |
31400 KB |
Output is correct |
73 |
Correct |
711 ms |
38468 KB |
Output is correct |
74 |
Correct |
743 ms |
38536 KB |
Output is correct |
75 |
Correct |
709 ms |
38496 KB |
Output is correct |
76 |
Correct |
753 ms |
38628 KB |
Output is correct |
77 |
Correct |
712 ms |
38420 KB |
Output is correct |
78 |
Correct |
724 ms |
38512 KB |
Output is correct |
79 |
Correct |
715 ms |
38504 KB |
Output is correct |
80 |
Correct |
722 ms |
38488 KB |
Output is correct |
81 |
Correct |
711 ms |
38644 KB |
Output is correct |
82 |
Correct |
716 ms |
38460 KB |
Output is correct |
83 |
Correct |
703 ms |
38472 KB |
Output is correct |
84 |
Correct |
705 ms |
38460 KB |
Output is correct |
85 |
Correct |
719 ms |
38432 KB |
Output is correct |
86 |
Correct |
684 ms |
38532 KB |
Output is correct |
87 |
Correct |
713 ms |
38484 KB |
Output is correct |
88 |
Correct |
747 ms |
38656 KB |
Output is correct |
89 |
Correct |
337 ms |
32472 KB |
Output is correct |
90 |
Correct |
708 ms |
38536 KB |
Output is correct |
91 |
Correct |
742 ms |
38316 KB |
Output is correct |
92 |
Correct |
243 ms |
29420 KB |
Output is correct |
93 |
Correct |
322 ms |
29900 KB |
Output is correct |
94 |
Correct |
235 ms |
29384 KB |
Output is correct |
95 |
Correct |
246 ms |
29484 KB |
Output is correct |
96 |
Correct |
313 ms |
29616 KB |
Output is correct |
97 |
Correct |
343 ms |
31472 KB |
Output is correct |
98 |
Correct |
226 ms |
29288 KB |
Output is correct |
99 |
Correct |
333 ms |
32820 KB |
Output is correct |
100 |
Correct |
237 ms |
29380 KB |
Output is correct |