#include <bits/stdc++.h>
#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()
using namespace std;
const int N = 1e5 + 5;
int n, m, x, y, w, ar[N], p[N], sz[N], up[20][N], mn[20][N], tin[N], tout[N], tiktak, h[N];
vector < vector <pair <int, int> > > g;
vector < vector <int> > r;
vector < pair <int, pair <int, int> > > vec;
priority_queue <pair <int, int> > q;
int get (int x)
{
return x == p[x] ? x : p[x] = get(p[x]);
}
void unite (int x, int y)
{
if (sz[x] > sz[y]) swap(x, y);
sz[y] += sz[x];
p[x] = y;
}
void dfs (int v, int pr = 0)
{
h[v] = h[pr] + 1;
tin[v] = ++tiktak;
up[0][v] = pr;
mn[0][v] = min(ar[pr], ar[v]);
for (int i = 1; i < 20; i++)
{
up[i][v] = up[i - 1][ up[i - 1][v] ];
mn[i][v] = min( mn[i - 1][v], mn[i - 1][ up[i - 1][v] ] );
}
for (auto to : r[v])
{
if (to == pr) continue;
dfs(to, v);
}
tout[v] = ++tiktak;
}
bool upper (int a, int b)
{
return tin[a] <= tin[b] && tout[b] <= tout[a];
}
int lca (int a, int b)
{
if(upper(a, b)) return a;
if(upper(b, a)) return b;
for (int i = 19; i >= 0; i--)
{
if ( up[i][a] && !upper( up[i][a], b ) )
a = up[i][a];
}
return up[0][a];
}
int minjump(int v, int d)
{
if (d == 0)
return ar[v];
int res = ar[v];
for (int i = 0; d; i++, d >>= 1) {
if (d & 1) {
res = min(res, mn[i][v]);
v = up[i][v];
}
}
return res;
}
int ans (int a, int b)
{
int c = lca(a, b);
return min( minjump( a, h[a] - h[c]), minjump( b, h[b] - h[c]) );
}
main()
{
cin >> n >> m;
g.resize(n + 1);
r.resize(n + 1);
for (int i = 1; i <= m; i++)
{
scanf("%d%d%d", &x, &y, &w);
g[x].pb( mk(y, w) );
g[y].pb( mk(x, w) );
}
memset( ar, 0x3f3f3f3f, sizeof(ar) );
cin >> m;
for (int i = 1; i <= m; i++)
{
scanf("%d", &x);
q.push( mk( 0, x ) );
ar[x] = 0;
}
while (!q.empty())
{
w = -q.top().fr, x = q.top().sc;
q.pop();
if (ar[x] < w) continue;
for (auto to : g[x])
{
if (ar[x] + to.sc < ar[to.fr])
{
ar[to.fr] = ar[x] + to.sc;
q.push( mk( -ar[to.fr], to.fr ) );
}
}
}
for (int i = 1; i <= n; i++)
{
p[i] = i;
sz[i] = 1;
for (auto to : g[i])
vec.pb( mk( min( ar[i], ar[to.fr] ), mk( i, to.fr ) ) );
}
sort( all(vec), greater < pair <int, pair <int, int> > >() );
for (auto it : vec)
{
x = it.sc.fr, y = it.sc.sc;
if (get(x) != get(y))
{
r[x].pb(y);
r[y].pb(x);
unite(get(x), get(y) );
}
}
dfs(1);
cin >> m;
while (m--)
{
scanf("%d%d", &x, &y);
printf("%d\n", ans(x, y));
}
}
Compilation message
plan.cpp:89:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main()
^
plan.cpp: In function 'int main()':
plan.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &x, &y, &w);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:105:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
~~~~~^~~~~~~~~~
plan.cpp:148:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
888 KB |
Output is correct |
2 |
Correct |
4 ms |
1272 KB |
Output is correct |
3 |
Correct |
4 ms |
1272 KB |
Output is correct |
4 |
Correct |
2 ms |
888 KB |
Output is correct |
5 |
Correct |
4 ms |
1272 KB |
Output is correct |
6 |
Correct |
4 ms |
1300 KB |
Output is correct |
7 |
Correct |
2 ms |
888 KB |
Output is correct |
8 |
Correct |
2 ms |
932 KB |
Output is correct |
9 |
Correct |
4 ms |
1324 KB |
Output is correct |
10 |
Correct |
4 ms |
1272 KB |
Output is correct |
11 |
Correct |
4 ms |
1196 KB |
Output is correct |
12 |
Correct |
4 ms |
1272 KB |
Output is correct |
13 |
Correct |
4 ms |
1272 KB |
Output is correct |
14 |
Correct |
4 ms |
1296 KB |
Output is correct |
15 |
Correct |
4 ms |
1276 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
888 KB |
Output is correct |
2 |
Correct |
4 ms |
1272 KB |
Output is correct |
3 |
Correct |
4 ms |
1272 KB |
Output is correct |
4 |
Correct |
2 ms |
888 KB |
Output is correct |
5 |
Correct |
4 ms |
1272 KB |
Output is correct |
6 |
Correct |
4 ms |
1300 KB |
Output is correct |
7 |
Correct |
2 ms |
888 KB |
Output is correct |
8 |
Correct |
2 ms |
932 KB |
Output is correct |
9 |
Correct |
4 ms |
1324 KB |
Output is correct |
10 |
Correct |
4 ms |
1272 KB |
Output is correct |
11 |
Correct |
4 ms |
1196 KB |
Output is correct |
12 |
Correct |
4 ms |
1272 KB |
Output is correct |
13 |
Correct |
4 ms |
1272 KB |
Output is correct |
14 |
Correct |
4 ms |
1296 KB |
Output is correct |
15 |
Correct |
4 ms |
1276 KB |
Output is correct |
16 |
Correct |
334 ms |
29112 KB |
Output is correct |
17 |
Correct |
945 ms |
54816 KB |
Output is correct |
18 |
Correct |
60 ms |
7020 KB |
Output is correct |
19 |
Correct |
193 ms |
36344 KB |
Output is correct |
20 |
Correct |
887 ms |
55120 KB |
Output is correct |
21 |
Correct |
498 ms |
39836 KB |
Output is correct |
22 |
Correct |
290 ms |
39036 KB |
Output is correct |
23 |
Correct |
877 ms |
55016 KB |
Output is correct |
24 |
Correct |
998 ms |
54724 KB |
Output is correct |
25 |
Correct |
853 ms |
54700 KB |
Output is correct |
26 |
Correct |
195 ms |
35556 KB |
Output is correct |
27 |
Correct |
190 ms |
35940 KB |
Output is correct |
28 |
Correct |
198 ms |
35808 KB |
Output is correct |
29 |
Correct |
195 ms |
36028 KB |
Output is correct |
30 |
Correct |
202 ms |
35940 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
888 KB |
Output is correct |
2 |
Correct |
2 ms |
888 KB |
Output is correct |
3 |
Correct |
2 ms |
888 KB |
Output is correct |
4 |
Correct |
3 ms |
888 KB |
Output is correct |
5 |
Correct |
3 ms |
888 KB |
Output is correct |
6 |
Correct |
3 ms |
1016 KB |
Output is correct |
7 |
Correct |
3 ms |
1016 KB |
Output is correct |
8 |
Correct |
3 ms |
888 KB |
Output is correct |
9 |
Correct |
3 ms |
888 KB |
Output is correct |
10 |
Correct |
3 ms |
1016 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
447 ms |
39168 KB |
Output is correct |
2 |
Correct |
789 ms |
54224 KB |
Output is correct |
3 |
Correct |
826 ms |
53800 KB |
Output is correct |
4 |
Correct |
237 ms |
35304 KB |
Output is correct |
5 |
Correct |
792 ms |
54096 KB |
Output is correct |
6 |
Correct |
851 ms |
54080 KB |
Output is correct |
7 |
Correct |
846 ms |
53856 KB |
Output is correct |
8 |
Correct |
809 ms |
53420 KB |
Output is correct |
9 |
Correct |
838 ms |
53360 KB |
Output is correct |
10 |
Correct |
836 ms |
53308 KB |
Output is correct |
11 |
Correct |
885 ms |
53460 KB |
Output is correct |
12 |
Correct |
830 ms |
53480 KB |
Output is correct |
13 |
Correct |
847 ms |
53460 KB |
Output is correct |
14 |
Correct |
825 ms |
53540 KB |
Output is correct |
15 |
Correct |
780 ms |
54176 KB |
Output is correct |
16 |
Correct |
813 ms |
53764 KB |
Output is correct |
17 |
Correct |
867 ms |
54176 KB |
Output is correct |
18 |
Correct |
856 ms |
53664 KB |
Output is correct |
19 |
Correct |
319 ms |
37196 KB |
Output is correct |
20 |
Correct |
837 ms |
54036 KB |
Output is correct |
21 |
Correct |
858 ms |
52780 KB |
Output is correct |
22 |
Correct |
152 ms |
34276 KB |
Output is correct |
23 |
Correct |
324 ms |
33800 KB |
Output is correct |
24 |
Correct |
158 ms |
34640 KB |
Output is correct |
25 |
Correct |
155 ms |
34404 KB |
Output is correct |
26 |
Correct |
306 ms |
34152 KB |
Output is correct |
27 |
Correct |
273 ms |
37032 KB |
Output is correct |
28 |
Correct |
153 ms |
34520 KB |
Output is correct |
29 |
Correct |
256 ms |
36104 KB |
Output is correct |
30 |
Correct |
156 ms |
34644 KB |
Output is correct |
31 |
Correct |
290 ms |
35944 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
888 KB |
Output is correct |
2 |
Correct |
4 ms |
1272 KB |
Output is correct |
3 |
Correct |
4 ms |
1272 KB |
Output is correct |
4 |
Correct |
2 ms |
888 KB |
Output is correct |
5 |
Correct |
4 ms |
1272 KB |
Output is correct |
6 |
Correct |
4 ms |
1300 KB |
Output is correct |
7 |
Correct |
2 ms |
888 KB |
Output is correct |
8 |
Correct |
2 ms |
932 KB |
Output is correct |
9 |
Correct |
4 ms |
1324 KB |
Output is correct |
10 |
Correct |
4 ms |
1272 KB |
Output is correct |
11 |
Correct |
4 ms |
1196 KB |
Output is correct |
12 |
Correct |
4 ms |
1272 KB |
Output is correct |
13 |
Correct |
4 ms |
1272 KB |
Output is correct |
14 |
Correct |
4 ms |
1296 KB |
Output is correct |
15 |
Correct |
4 ms |
1276 KB |
Output is correct |
16 |
Correct |
334 ms |
29112 KB |
Output is correct |
17 |
Correct |
945 ms |
54816 KB |
Output is correct |
18 |
Correct |
60 ms |
7020 KB |
Output is correct |
19 |
Correct |
193 ms |
36344 KB |
Output is correct |
20 |
Correct |
887 ms |
55120 KB |
Output is correct |
21 |
Correct |
498 ms |
39836 KB |
Output is correct |
22 |
Correct |
290 ms |
39036 KB |
Output is correct |
23 |
Correct |
877 ms |
55016 KB |
Output is correct |
24 |
Correct |
998 ms |
54724 KB |
Output is correct |
25 |
Correct |
853 ms |
54700 KB |
Output is correct |
26 |
Correct |
195 ms |
35556 KB |
Output is correct |
27 |
Correct |
190 ms |
35940 KB |
Output is correct |
28 |
Correct |
198 ms |
35808 KB |
Output is correct |
29 |
Correct |
195 ms |
36028 KB |
Output is correct |
30 |
Correct |
202 ms |
35940 KB |
Output is correct |
31 |
Correct |
2 ms |
888 KB |
Output is correct |
32 |
Correct |
2 ms |
888 KB |
Output is correct |
33 |
Correct |
2 ms |
888 KB |
Output is correct |
34 |
Correct |
3 ms |
888 KB |
Output is correct |
35 |
Correct |
3 ms |
888 KB |
Output is correct |
36 |
Correct |
3 ms |
1016 KB |
Output is correct |
37 |
Correct |
3 ms |
1016 KB |
Output is correct |
38 |
Correct |
3 ms |
888 KB |
Output is correct |
39 |
Correct |
3 ms |
888 KB |
Output is correct |
40 |
Correct |
3 ms |
1016 KB |
Output is correct |
41 |
Correct |
447 ms |
39168 KB |
Output is correct |
42 |
Correct |
789 ms |
54224 KB |
Output is correct |
43 |
Correct |
826 ms |
53800 KB |
Output is correct |
44 |
Correct |
237 ms |
35304 KB |
Output is correct |
45 |
Correct |
792 ms |
54096 KB |
Output is correct |
46 |
Correct |
851 ms |
54080 KB |
Output is correct |
47 |
Correct |
846 ms |
53856 KB |
Output is correct |
48 |
Correct |
809 ms |
53420 KB |
Output is correct |
49 |
Correct |
838 ms |
53360 KB |
Output is correct |
50 |
Correct |
836 ms |
53308 KB |
Output is correct |
51 |
Correct |
885 ms |
53460 KB |
Output is correct |
52 |
Correct |
830 ms |
53480 KB |
Output is correct |
53 |
Correct |
847 ms |
53460 KB |
Output is correct |
54 |
Correct |
825 ms |
53540 KB |
Output is correct |
55 |
Correct |
780 ms |
54176 KB |
Output is correct |
56 |
Correct |
813 ms |
53764 KB |
Output is correct |
57 |
Correct |
867 ms |
54176 KB |
Output is correct |
58 |
Correct |
856 ms |
53664 KB |
Output is correct |
59 |
Correct |
319 ms |
37196 KB |
Output is correct |
60 |
Correct |
837 ms |
54036 KB |
Output is correct |
61 |
Correct |
858 ms |
52780 KB |
Output is correct |
62 |
Correct |
152 ms |
34276 KB |
Output is correct |
63 |
Correct |
324 ms |
33800 KB |
Output is correct |
64 |
Correct |
158 ms |
34640 KB |
Output is correct |
65 |
Correct |
155 ms |
34404 KB |
Output is correct |
66 |
Correct |
306 ms |
34152 KB |
Output is correct |
67 |
Correct |
273 ms |
37032 KB |
Output is correct |
68 |
Correct |
153 ms |
34520 KB |
Output is correct |
69 |
Correct |
256 ms |
36104 KB |
Output is correct |
70 |
Correct |
156 ms |
34644 KB |
Output is correct |
71 |
Correct |
290 ms |
35944 KB |
Output is correct |
72 |
Correct |
553 ms |
39760 KB |
Output is correct |
73 |
Correct |
899 ms |
53472 KB |
Output is correct |
74 |
Correct |
853 ms |
51972 KB |
Output is correct |
75 |
Correct |
871 ms |
51948 KB |
Output is correct |
76 |
Correct |
936 ms |
52040 KB |
Output is correct |
77 |
Correct |
946 ms |
51972 KB |
Output is correct |
78 |
Correct |
953 ms |
52112 KB |
Output is correct |
79 |
Correct |
864 ms |
51980 KB |
Output is correct |
80 |
Correct |
871 ms |
51972 KB |
Output is correct |
81 |
Correct |
875 ms |
52008 KB |
Output is correct |
82 |
Correct |
863 ms |
51916 KB |
Output is correct |
83 |
Correct |
922 ms |
51956 KB |
Output is correct |
84 |
Correct |
943 ms |
51976 KB |
Output is correct |
85 |
Correct |
919 ms |
51880 KB |
Output is correct |
86 |
Correct |
1010 ms |
51892 KB |
Output is correct |
87 |
Correct |
916 ms |
51936 KB |
Output is correct |
88 |
Correct |
902 ms |
52012 KB |
Output is correct |
89 |
Correct |
411 ms |
36152 KB |
Output is correct |
90 |
Correct |
931 ms |
51988 KB |
Output is correct |
91 |
Correct |
805 ms |
51496 KB |
Output is correct |
92 |
Correct |
210 ms |
33920 KB |
Output is correct |
93 |
Correct |
405 ms |
33644 KB |
Output is correct |
94 |
Correct |
207 ms |
33832 KB |
Output is correct |
95 |
Correct |
202 ms |
34020 KB |
Output is correct |
96 |
Correct |
448 ms |
33500 KB |
Output is correct |
97 |
Correct |
383 ms |
35208 KB |
Output is correct |
98 |
Correct |
210 ms |
33912 KB |
Output is correct |
99 |
Correct |
391 ms |
36424 KB |
Output is correct |
100 |
Correct |
215 ms |
34304 KB |
Output is correct |