#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e5+10;
const int inf = 1e9+10;
int n;
int pai[maxn], peso[maxn], edge[maxn], tt;
int nivel[maxn];
bool city[maxn], mark[maxn];
pii dist[maxn];
vector<pii> grafo[maxn];
void dijkstra(void)
{
for (int i = 1; i <= n; i++)
dist[i] = {inf, i};
priority_queue<pii, vector<pii>, greater<pii>> fila;
for (int i = 1; i <= n; i++)
{
if (city[i])
{
fila.push({0, i});
dist[i] = {0, i};
}
}
while (!fila.empty())
{
int u = fila.top().second; fila.pop();
if (mark[u]) continue;
mark[u] = 1;
for (auto pp: grafo[u])
{
int v = pp.first, w = pp.second;
if (dist[v].first > dist[u].first+w)
{
dist[v].first = dist[u].first+w;
fila.push(dist[v]);
}
}
}
}
void init(void)
{
for (int i = 1; i <= n; i++)
pai[i] = i, peso[i] = 1, edge[i] = 1;
}
int Find(int x)
{
if (pai[x] == x) return x;
return Find(pai[x]);
}
void Join(int x, int y)
{
x = Find(x), y = Find(y);
if (x == y) return;
if (peso[x] < peso[y]) swap(x, y);
pai[y] = x, peso[x] += peso[y], edge[y] = tt;
}
int dfs(int u)
{
mark[u] = 1;
if (u == Find(u)) return 0;
if (mark[pai[u]]) return (nivel[u] = nivel[pai[u]]+1);
return (nivel[u] = dfs(pai[u])+1);
}
int get(int u, int v)
{
int ans = 1;
while (u != v)
{
if (nivel[u] > nivel[v]) ans = max(ans, edge[u]), u = pai[u];
else ans = max(ans, edge[v]), v = pai[v];
}
return ans;
}
bool comp(pii a, pii b) {return a.first > b.first;}
int main(void)
{
int m;
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++)
{
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
grafo[u].push_back({v, w});
grafo[v].push_back({u, w});
}
int k;
scanf("%d", &k);
for (int i = 1; i <= k; i++)
{
int u;
scanf("%d", &u);
city[u] = 1;
}
dijkstra();
sort(dist+1, dist+n+1, comp);
memset(mark, 0, sizeof mark);
init();
for (int i = 1; i <= n; i++)
{
int u = dist[i].second;
++tt;
for (auto pp: grafo[u])
{
int v = pp.first;
if (mark[v])
Join(u, v);
}
mark[u] = 1;
}
memset(mark, 0, sizeof mark);
for (int i = 1; i <= n; i++)
if (!mark[i])
dfs(i);
int q;
scanf("%d", &q);
for (int i = 1; i <= q; i++)
{
int u, v;
scanf("%d %d", &u, &v);
printf("%d\n", dist[get(u, v)].first);
}
}
Compilation message
plan.cpp: In function 'int main()':
plan.cpp:108: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:113:8: 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:120:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &k);
~~~~~^~~~~~~~~~
plan.cpp:125:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &u);
~~~~~^~~~~~~~~~
plan.cpp:162:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
plan.cpp:167:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &u, &v);
~~~~~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2808 KB |
Output is correct |
2 |
Correct |
5 ms |
2812 KB |
Output is correct |
3 |
Correct |
5 ms |
2812 KB |
Output is correct |
4 |
Correct |
4 ms |
2808 KB |
Output is correct |
5 |
Correct |
5 ms |
2808 KB |
Output is correct |
6 |
Correct |
5 ms |
2808 KB |
Output is correct |
7 |
Correct |
4 ms |
2808 KB |
Output is correct |
8 |
Correct |
4 ms |
2808 KB |
Output is correct |
9 |
Correct |
5 ms |
2888 KB |
Output is correct |
10 |
Correct |
5 ms |
2936 KB |
Output is correct |
11 |
Correct |
5 ms |
2812 KB |
Output is correct |
12 |
Correct |
5 ms |
2808 KB |
Output is correct |
13 |
Correct |
5 ms |
2892 KB |
Output is correct |
14 |
Correct |
5 ms |
2812 KB |
Output is correct |
15 |
Correct |
5 ms |
2808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2808 KB |
Output is correct |
2 |
Correct |
5 ms |
2812 KB |
Output is correct |
3 |
Correct |
5 ms |
2812 KB |
Output is correct |
4 |
Correct |
4 ms |
2808 KB |
Output is correct |
5 |
Correct |
5 ms |
2808 KB |
Output is correct |
6 |
Correct |
5 ms |
2808 KB |
Output is correct |
7 |
Correct |
4 ms |
2808 KB |
Output is correct |
8 |
Correct |
4 ms |
2808 KB |
Output is correct |
9 |
Correct |
5 ms |
2888 KB |
Output is correct |
10 |
Correct |
5 ms |
2936 KB |
Output is correct |
11 |
Correct |
5 ms |
2812 KB |
Output is correct |
12 |
Correct |
5 ms |
2808 KB |
Output is correct |
13 |
Correct |
5 ms |
2892 KB |
Output is correct |
14 |
Correct |
5 ms |
2812 KB |
Output is correct |
15 |
Correct |
5 ms |
2808 KB |
Output is correct |
16 |
Correct |
155 ms |
9072 KB |
Output is correct |
17 |
Correct |
549 ms |
20320 KB |
Output is correct |
18 |
Correct |
38 ms |
4624 KB |
Output is correct |
19 |
Correct |
148 ms |
9944 KB |
Output is correct |
20 |
Correct |
524 ms |
20420 KB |
Output is correct |
21 |
Correct |
252 ms |
12344 KB |
Output is correct |
22 |
Correct |
147 ms |
9336 KB |
Output is correct |
23 |
Correct |
543 ms |
20392 KB |
Output is correct |
24 |
Correct |
541 ms |
20284 KB |
Output is correct |
25 |
Correct |
543 ms |
20140 KB |
Output is correct |
26 |
Correct |
140 ms |
9696 KB |
Output is correct |
27 |
Correct |
141 ms |
9808 KB |
Output is correct |
28 |
Correct |
146 ms |
9692 KB |
Output is correct |
29 |
Correct |
142 ms |
9816 KB |
Output is correct |
30 |
Correct |
146 ms |
9828 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2808 KB |
Output is correct |
2 |
Correct |
4 ms |
2808 KB |
Output is correct |
3 |
Correct |
4 ms |
2808 KB |
Output is correct |
4 |
Correct |
4 ms |
2808 KB |
Output is correct |
5 |
Correct |
4 ms |
2808 KB |
Output is correct |
6 |
Correct |
4 ms |
2808 KB |
Output is correct |
7 |
Correct |
4 ms |
2808 KB |
Output is correct |
8 |
Correct |
4 ms |
2808 KB |
Output is correct |
9 |
Correct |
4 ms |
2808 KB |
Output is correct |
10 |
Correct |
4 ms |
2808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
212 ms |
12108 KB |
Output is correct |
2 |
Correct |
482 ms |
19904 KB |
Output is correct |
3 |
Correct |
485 ms |
20132 KB |
Output is correct |
4 |
Correct |
97 ms |
8628 KB |
Output is correct |
5 |
Correct |
469 ms |
19976 KB |
Output is correct |
6 |
Correct |
513 ms |
20148 KB |
Output is correct |
7 |
Correct |
550 ms |
20156 KB |
Output is correct |
8 |
Correct |
528 ms |
19992 KB |
Output is correct |
9 |
Correct |
497 ms |
19976 KB |
Output is correct |
10 |
Correct |
470 ms |
20036 KB |
Output is correct |
11 |
Correct |
500 ms |
19784 KB |
Output is correct |
12 |
Correct |
485 ms |
20080 KB |
Output is correct |
13 |
Correct |
479 ms |
20016 KB |
Output is correct |
14 |
Correct |
468 ms |
20044 KB |
Output is correct |
15 |
Correct |
496 ms |
20588 KB |
Output is correct |
16 |
Correct |
482 ms |
19840 KB |
Output is correct |
17 |
Correct |
473 ms |
19944 KB |
Output is correct |
18 |
Correct |
475 ms |
19960 KB |
Output is correct |
19 |
Correct |
108 ms |
8352 KB |
Output is correct |
20 |
Correct |
484 ms |
19772 KB |
Output is correct |
21 |
Correct |
459 ms |
19460 KB |
Output is correct |
22 |
Correct |
103 ms |
9304 KB |
Output is correct |
23 |
Correct |
105 ms |
8924 KB |
Output is correct |
24 |
Correct |
99 ms |
9176 KB |
Output is correct |
25 |
Correct |
106 ms |
9148 KB |
Output is correct |
26 |
Correct |
108 ms |
8996 KB |
Output is correct |
27 |
Correct |
103 ms |
8256 KB |
Output is correct |
28 |
Correct |
100 ms |
9188 KB |
Output is correct |
29 |
Correct |
91 ms |
8232 KB |
Output is correct |
30 |
Correct |
105 ms |
9276 KB |
Output is correct |
31 |
Correct |
96 ms |
8184 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2808 KB |
Output is correct |
2 |
Correct |
5 ms |
2812 KB |
Output is correct |
3 |
Correct |
5 ms |
2812 KB |
Output is correct |
4 |
Correct |
4 ms |
2808 KB |
Output is correct |
5 |
Correct |
5 ms |
2808 KB |
Output is correct |
6 |
Correct |
5 ms |
2808 KB |
Output is correct |
7 |
Correct |
4 ms |
2808 KB |
Output is correct |
8 |
Correct |
4 ms |
2808 KB |
Output is correct |
9 |
Correct |
5 ms |
2888 KB |
Output is correct |
10 |
Correct |
5 ms |
2936 KB |
Output is correct |
11 |
Correct |
5 ms |
2812 KB |
Output is correct |
12 |
Correct |
5 ms |
2808 KB |
Output is correct |
13 |
Correct |
5 ms |
2892 KB |
Output is correct |
14 |
Correct |
5 ms |
2812 KB |
Output is correct |
15 |
Correct |
5 ms |
2808 KB |
Output is correct |
16 |
Correct |
155 ms |
9072 KB |
Output is correct |
17 |
Correct |
549 ms |
20320 KB |
Output is correct |
18 |
Correct |
38 ms |
4624 KB |
Output is correct |
19 |
Correct |
148 ms |
9944 KB |
Output is correct |
20 |
Correct |
524 ms |
20420 KB |
Output is correct |
21 |
Correct |
252 ms |
12344 KB |
Output is correct |
22 |
Correct |
147 ms |
9336 KB |
Output is correct |
23 |
Correct |
543 ms |
20392 KB |
Output is correct |
24 |
Correct |
541 ms |
20284 KB |
Output is correct |
25 |
Correct |
543 ms |
20140 KB |
Output is correct |
26 |
Correct |
140 ms |
9696 KB |
Output is correct |
27 |
Correct |
141 ms |
9808 KB |
Output is correct |
28 |
Correct |
146 ms |
9692 KB |
Output is correct |
29 |
Correct |
142 ms |
9816 KB |
Output is correct |
30 |
Correct |
146 ms |
9828 KB |
Output is correct |
31 |
Correct |
4 ms |
2808 KB |
Output is correct |
32 |
Correct |
4 ms |
2808 KB |
Output is correct |
33 |
Correct |
4 ms |
2808 KB |
Output is correct |
34 |
Correct |
4 ms |
2808 KB |
Output is correct |
35 |
Correct |
4 ms |
2808 KB |
Output is correct |
36 |
Correct |
4 ms |
2808 KB |
Output is correct |
37 |
Correct |
4 ms |
2808 KB |
Output is correct |
38 |
Correct |
4 ms |
2808 KB |
Output is correct |
39 |
Correct |
4 ms |
2808 KB |
Output is correct |
40 |
Correct |
4 ms |
2808 KB |
Output is correct |
41 |
Correct |
212 ms |
12108 KB |
Output is correct |
42 |
Correct |
482 ms |
19904 KB |
Output is correct |
43 |
Correct |
485 ms |
20132 KB |
Output is correct |
44 |
Correct |
97 ms |
8628 KB |
Output is correct |
45 |
Correct |
469 ms |
19976 KB |
Output is correct |
46 |
Correct |
513 ms |
20148 KB |
Output is correct |
47 |
Correct |
550 ms |
20156 KB |
Output is correct |
48 |
Correct |
528 ms |
19992 KB |
Output is correct |
49 |
Correct |
497 ms |
19976 KB |
Output is correct |
50 |
Correct |
470 ms |
20036 KB |
Output is correct |
51 |
Correct |
500 ms |
19784 KB |
Output is correct |
52 |
Correct |
485 ms |
20080 KB |
Output is correct |
53 |
Correct |
479 ms |
20016 KB |
Output is correct |
54 |
Correct |
468 ms |
20044 KB |
Output is correct |
55 |
Correct |
496 ms |
20588 KB |
Output is correct |
56 |
Correct |
482 ms |
19840 KB |
Output is correct |
57 |
Correct |
473 ms |
19944 KB |
Output is correct |
58 |
Correct |
475 ms |
19960 KB |
Output is correct |
59 |
Correct |
108 ms |
8352 KB |
Output is correct |
60 |
Correct |
484 ms |
19772 KB |
Output is correct |
61 |
Correct |
459 ms |
19460 KB |
Output is correct |
62 |
Correct |
103 ms |
9304 KB |
Output is correct |
63 |
Correct |
105 ms |
8924 KB |
Output is correct |
64 |
Correct |
99 ms |
9176 KB |
Output is correct |
65 |
Correct |
106 ms |
9148 KB |
Output is correct |
66 |
Correct |
108 ms |
8996 KB |
Output is correct |
67 |
Correct |
103 ms |
8256 KB |
Output is correct |
68 |
Correct |
100 ms |
9188 KB |
Output is correct |
69 |
Correct |
91 ms |
8232 KB |
Output is correct |
70 |
Correct |
105 ms |
9276 KB |
Output is correct |
71 |
Correct |
96 ms |
8184 KB |
Output is correct |
72 |
Correct |
257 ms |
12232 KB |
Output is correct |
73 |
Correct |
529 ms |
19864 KB |
Output is correct |
74 |
Correct |
536 ms |
19720 KB |
Output is correct |
75 |
Correct |
543 ms |
19888 KB |
Output is correct |
76 |
Correct |
544 ms |
19968 KB |
Output is correct |
77 |
Correct |
524 ms |
19788 KB |
Output is correct |
78 |
Correct |
509 ms |
19912 KB |
Output is correct |
79 |
Correct |
521 ms |
19848 KB |
Output is correct |
80 |
Correct |
535 ms |
19732 KB |
Output is correct |
81 |
Correct |
526 ms |
19684 KB |
Output is correct |
82 |
Correct |
512 ms |
19892 KB |
Output is correct |
83 |
Correct |
529 ms |
20284 KB |
Output is correct |
84 |
Correct |
543 ms |
20340 KB |
Output is correct |
85 |
Correct |
552 ms |
20088 KB |
Output is correct |
86 |
Correct |
533 ms |
20432 KB |
Output is correct |
87 |
Correct |
529 ms |
20252 KB |
Output is correct |
88 |
Correct |
544 ms |
20228 KB |
Output is correct |
89 |
Correct |
183 ms |
9492 KB |
Output is correct |
90 |
Correct |
560 ms |
20268 KB |
Output is correct |
91 |
Correct |
565 ms |
19564 KB |
Output is correct |
92 |
Correct |
149 ms |
9552 KB |
Output is correct |
93 |
Correct |
168 ms |
9464 KB |
Output is correct |
94 |
Correct |
148 ms |
9436 KB |
Output is correct |
95 |
Correct |
144 ms |
9552 KB |
Output is correct |
96 |
Correct |
164 ms |
9232 KB |
Output is correct |
97 |
Correct |
146 ms |
8824 KB |
Output is correct |
98 |
Correct |
141 ms |
9440 KB |
Output is correct |
99 |
Correct |
140 ms |
8824 KB |
Output is correct |
100 |
Correct |
145 ms |
9556 KB |
Output is correct |