#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
const int INF=0x3f3f3f3f;
const int N=1e5+5;
const int LOG=18;
int n, m, k, q;
int dist[N], P[N], dep[N];
vector <pii> ls[N], ls_st[N];
set <pii> S;
vector <pip> v;
int par[LOG][N], val[LOG][N];
int name(int x) {
if (x==P[x]) return x;
P[x]=name(P[x]);
return P[x];
}
int mrg(int a, int b) {
a=name(a); b=name(b);
if (a==b) return 0;
P[a]=b;
return 1;
}
void build() {
for (int i=1; i<LOG; ++i) {
for (int j=1; j<=n; ++j) {
par[i][j]=par[i-1][par[i-1][j]];
val[i][j]=min(val[i-1][j], val[i-1][par[i-1][j]]);
}
}
}
int lca(int x, int y) {
if (dep[x]<dep[y]) swap(x, y);
for (int i=LOG-1; i>=0; --i) {
if (dep[x]-(1<<i)>=dep[y]) x=par[i][x];
}
if (x==y) return x;
for (int i=LOG-1; i>=0; --i) {
if (par[i][x]!=par[i][y]) x=par[i][x], y=par[i][y];
}
return par[0][x];
}
int popni(int x, int d) {
int ret=INF;
for (int i=LOG-1; i>=0; --i) {
if (dep[x]-(1<<i)>=d) {
ret=min(ret, val[i][x]);
x=par[i][x];
}
}
return ret;
}
void dfs(int node, int rod) {
dep[node]=dep[rod]+1;
par[0][node]=rod;
for (pii sus:ls_st[node]) {
if (sus.X==rod) continue;
dfs(sus.X, node);
val[0][sus.X]=sus.Y;
}
}
void dijkstra() {
while (!S.empty()) {
pii node=*S.begin();
S.erase(S.begin());
for (pii sus:ls[node.Y]) {
if (dist[sus.X]<=sus.Y+node.X) continue;
if (S.count(mp(dist[sus.X], sus.X))) S.erase(mp(dist[sus.X], sus.X));
dist[sus.X]=sus.Y+node.X;
S.insert(mp(dist[sus.X], sus.X));
}
}
}
void solve() {
dijkstra();
for (int i=1; i<=n; ++i) {
P[i]=i;
for (pii sus:ls[i]) {
int ed=min(dist[i], dist[sus.X]);
if (sus.X>i) v.pb(mp(ed, mp(i, sus.X)));
}
}
sort(v.begin(), v.end());
reverse(v.begin(), v.end());
for (int i=0; i<v.size(); ++i) {
if (mrg(v[i].Y.X, v[i].Y.Y)) {
ls_st[v[i].Y.X].pb(mp(v[i].Y.Y, v[i].X));
ls_st[v[i].Y.Y].pb(mp(v[i].Y.X, v[i].X));
}
}
dfs(1, 0);
build();
for (int i=0; i<q; ++i) {
int a, b;
scanf("%d %d", &a, &b);
int lc=lca(a, b);
printf("%d\n", min(popni(a, dep[lc]), popni(b, dep[lc])));
}
}
void load() {
scanf("%d %d", &n, &m);
for (int i=0; i<m; ++i) {
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
ls[a].pb(mp(b, c));
ls[b].pb(mp(a, c));
}
scanf("%d", &k);
memset(dist, INF, sizeof dist);
for (int i=0; i<k; ++i) {
int x;
scanf("%d", &x);
S.insert(mp(0, x));
dist[x]=0;
}
scanf("%d", &q);
}
int main() {
load();
solve();
return 0;
}
Compilation message
plan.cpp: In function 'void solve()':
plan.cpp:105:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for (int i=0; i<v.size(); ++i) {
| ~^~~~~~~~~
plan.cpp:115:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
115 | scanf("%d %d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~
plan.cpp: In function 'void load()':
plan.cpp:122:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
122 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
plan.cpp:125:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
125 | scanf("%d %d %d", &a, &b, &c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:129:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
129 | scanf("%d", &k);
| ~~~~~^~~~~~~~~~
plan.cpp:133:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
133 | scanf("%d", &x);
| ~~~~~^~~~~~~~~~
plan.cpp:137:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
137 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
5612 KB |
Output is correct |
2 |
Correct |
6 ms |
5868 KB |
Output is correct |
3 |
Correct |
7 ms |
5868 KB |
Output is correct |
4 |
Correct |
4 ms |
5612 KB |
Output is correct |
5 |
Correct |
6 ms |
5868 KB |
Output is correct |
6 |
Correct |
6 ms |
5868 KB |
Output is correct |
7 |
Correct |
5 ms |
5612 KB |
Output is correct |
8 |
Correct |
5 ms |
5612 KB |
Output is correct |
9 |
Correct |
6 ms |
5868 KB |
Output is correct |
10 |
Correct |
6 ms |
5868 KB |
Output is correct |
11 |
Correct |
8 ms |
5868 KB |
Output is correct |
12 |
Correct |
6 ms |
5868 KB |
Output is correct |
13 |
Correct |
6 ms |
5868 KB |
Output is correct |
14 |
Correct |
6 ms |
5868 KB |
Output is correct |
15 |
Correct |
6 ms |
5868 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
5612 KB |
Output is correct |
2 |
Correct |
6 ms |
5868 KB |
Output is correct |
3 |
Correct |
7 ms |
5868 KB |
Output is correct |
4 |
Correct |
4 ms |
5612 KB |
Output is correct |
5 |
Correct |
6 ms |
5868 KB |
Output is correct |
6 |
Correct |
6 ms |
5868 KB |
Output is correct |
7 |
Correct |
5 ms |
5612 KB |
Output is correct |
8 |
Correct |
5 ms |
5612 KB |
Output is correct |
9 |
Correct |
6 ms |
5868 KB |
Output is correct |
10 |
Correct |
6 ms |
5868 KB |
Output is correct |
11 |
Correct |
8 ms |
5868 KB |
Output is correct |
12 |
Correct |
6 ms |
5868 KB |
Output is correct |
13 |
Correct |
6 ms |
5868 KB |
Output is correct |
14 |
Correct |
6 ms |
5868 KB |
Output is correct |
15 |
Correct |
6 ms |
5868 KB |
Output is correct |
16 |
Correct |
228 ms |
27748 KB |
Output is correct |
17 |
Correct |
828 ms |
52452 KB |
Output is correct |
18 |
Correct |
46 ms |
10276 KB |
Output is correct |
19 |
Correct |
190 ms |
33120 KB |
Output is correct |
20 |
Correct |
906 ms |
52572 KB |
Output is correct |
21 |
Correct |
412 ms |
37220 KB |
Output is correct |
22 |
Correct |
165 ms |
37732 KB |
Output is correct |
23 |
Correct |
895 ms |
52340 KB |
Output is correct |
24 |
Correct |
884 ms |
52320 KB |
Output is correct |
25 |
Correct |
885 ms |
52244 KB |
Output is correct |
26 |
Correct |
197 ms |
33120 KB |
Output is correct |
27 |
Correct |
221 ms |
33248 KB |
Output is correct |
28 |
Correct |
192 ms |
33116 KB |
Output is correct |
29 |
Correct |
187 ms |
32860 KB |
Output is correct |
30 |
Correct |
223 ms |
33376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
5612 KB |
Output is correct |
2 |
Correct |
5 ms |
5612 KB |
Output is correct |
3 |
Correct |
4 ms |
5612 KB |
Output is correct |
4 |
Correct |
5 ms |
5612 KB |
Output is correct |
5 |
Correct |
5 ms |
5612 KB |
Output is correct |
6 |
Correct |
5 ms |
5612 KB |
Output is correct |
7 |
Correct |
4 ms |
5612 KB |
Output is correct |
8 |
Correct |
5 ms |
5612 KB |
Output is correct |
9 |
Correct |
5 ms |
5612 KB |
Output is correct |
10 |
Correct |
5 ms |
5612 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
325 ms |
35548 KB |
Output is correct |
2 |
Correct |
792 ms |
50524 KB |
Output is correct |
3 |
Correct |
715 ms |
50524 KB |
Output is correct |
4 |
Correct |
116 ms |
33252 KB |
Output is correct |
5 |
Correct |
752 ms |
50656 KB |
Output is correct |
6 |
Correct |
715 ms |
50780 KB |
Output is correct |
7 |
Correct |
754 ms |
50692 KB |
Output is correct |
8 |
Correct |
735 ms |
50592 KB |
Output is correct |
9 |
Correct |
755 ms |
50784 KB |
Output is correct |
10 |
Correct |
761 ms |
50620 KB |
Output is correct |
11 |
Correct |
712 ms |
50780 KB |
Output is correct |
12 |
Correct |
736 ms |
50736 KB |
Output is correct |
13 |
Correct |
711 ms |
50652 KB |
Output is correct |
14 |
Correct |
719 ms |
50600 KB |
Output is correct |
15 |
Correct |
714 ms |
50892 KB |
Output is correct |
16 |
Correct |
742 ms |
50588 KB |
Output is correct |
17 |
Correct |
728 ms |
50780 KB |
Output is correct |
18 |
Correct |
712 ms |
50652 KB |
Output is correct |
19 |
Correct |
114 ms |
35300 KB |
Output is correct |
20 |
Correct |
724 ms |
50656 KB |
Output is correct |
21 |
Correct |
589 ms |
51552 KB |
Output is correct |
22 |
Correct |
145 ms |
31712 KB |
Output is correct |
23 |
Correct |
135 ms |
30968 KB |
Output is correct |
24 |
Correct |
151 ms |
31712 KB |
Output is correct |
25 |
Correct |
143 ms |
31328 KB |
Output is correct |
26 |
Correct |
163 ms |
31520 KB |
Output is correct |
27 |
Correct |
116 ms |
35044 KB |
Output is correct |
28 |
Correct |
147 ms |
31836 KB |
Output is correct |
29 |
Correct |
119 ms |
34148 KB |
Output is correct |
30 |
Correct |
143 ms |
31712 KB |
Output is correct |
31 |
Correct |
114 ms |
34172 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
5612 KB |
Output is correct |
2 |
Correct |
6 ms |
5868 KB |
Output is correct |
3 |
Correct |
7 ms |
5868 KB |
Output is correct |
4 |
Correct |
4 ms |
5612 KB |
Output is correct |
5 |
Correct |
6 ms |
5868 KB |
Output is correct |
6 |
Correct |
6 ms |
5868 KB |
Output is correct |
7 |
Correct |
5 ms |
5612 KB |
Output is correct |
8 |
Correct |
5 ms |
5612 KB |
Output is correct |
9 |
Correct |
6 ms |
5868 KB |
Output is correct |
10 |
Correct |
6 ms |
5868 KB |
Output is correct |
11 |
Correct |
8 ms |
5868 KB |
Output is correct |
12 |
Correct |
6 ms |
5868 KB |
Output is correct |
13 |
Correct |
6 ms |
5868 KB |
Output is correct |
14 |
Correct |
6 ms |
5868 KB |
Output is correct |
15 |
Correct |
6 ms |
5868 KB |
Output is correct |
16 |
Correct |
228 ms |
27748 KB |
Output is correct |
17 |
Correct |
828 ms |
52452 KB |
Output is correct |
18 |
Correct |
46 ms |
10276 KB |
Output is correct |
19 |
Correct |
190 ms |
33120 KB |
Output is correct |
20 |
Correct |
906 ms |
52572 KB |
Output is correct |
21 |
Correct |
412 ms |
37220 KB |
Output is correct |
22 |
Correct |
165 ms |
37732 KB |
Output is correct |
23 |
Correct |
895 ms |
52340 KB |
Output is correct |
24 |
Correct |
884 ms |
52320 KB |
Output is correct |
25 |
Correct |
885 ms |
52244 KB |
Output is correct |
26 |
Correct |
197 ms |
33120 KB |
Output is correct |
27 |
Correct |
221 ms |
33248 KB |
Output is correct |
28 |
Correct |
192 ms |
33116 KB |
Output is correct |
29 |
Correct |
187 ms |
32860 KB |
Output is correct |
30 |
Correct |
223 ms |
33376 KB |
Output is correct |
31 |
Correct |
5 ms |
5612 KB |
Output is correct |
32 |
Correct |
5 ms |
5612 KB |
Output is correct |
33 |
Correct |
4 ms |
5612 KB |
Output is correct |
34 |
Correct |
5 ms |
5612 KB |
Output is correct |
35 |
Correct |
5 ms |
5612 KB |
Output is correct |
36 |
Correct |
5 ms |
5612 KB |
Output is correct |
37 |
Correct |
4 ms |
5612 KB |
Output is correct |
38 |
Correct |
5 ms |
5612 KB |
Output is correct |
39 |
Correct |
5 ms |
5612 KB |
Output is correct |
40 |
Correct |
5 ms |
5612 KB |
Output is correct |
41 |
Correct |
325 ms |
35548 KB |
Output is correct |
42 |
Correct |
792 ms |
50524 KB |
Output is correct |
43 |
Correct |
715 ms |
50524 KB |
Output is correct |
44 |
Correct |
116 ms |
33252 KB |
Output is correct |
45 |
Correct |
752 ms |
50656 KB |
Output is correct |
46 |
Correct |
715 ms |
50780 KB |
Output is correct |
47 |
Correct |
754 ms |
50692 KB |
Output is correct |
48 |
Correct |
735 ms |
50592 KB |
Output is correct |
49 |
Correct |
755 ms |
50784 KB |
Output is correct |
50 |
Correct |
761 ms |
50620 KB |
Output is correct |
51 |
Correct |
712 ms |
50780 KB |
Output is correct |
52 |
Correct |
736 ms |
50736 KB |
Output is correct |
53 |
Correct |
711 ms |
50652 KB |
Output is correct |
54 |
Correct |
719 ms |
50600 KB |
Output is correct |
55 |
Correct |
714 ms |
50892 KB |
Output is correct |
56 |
Correct |
742 ms |
50588 KB |
Output is correct |
57 |
Correct |
728 ms |
50780 KB |
Output is correct |
58 |
Correct |
712 ms |
50652 KB |
Output is correct |
59 |
Correct |
114 ms |
35300 KB |
Output is correct |
60 |
Correct |
724 ms |
50656 KB |
Output is correct |
61 |
Correct |
589 ms |
51552 KB |
Output is correct |
62 |
Correct |
145 ms |
31712 KB |
Output is correct |
63 |
Correct |
135 ms |
30968 KB |
Output is correct |
64 |
Correct |
151 ms |
31712 KB |
Output is correct |
65 |
Correct |
143 ms |
31328 KB |
Output is correct |
66 |
Correct |
163 ms |
31520 KB |
Output is correct |
67 |
Correct |
116 ms |
35044 KB |
Output is correct |
68 |
Correct |
147 ms |
31836 KB |
Output is correct |
69 |
Correct |
119 ms |
34148 KB |
Output is correct |
70 |
Correct |
143 ms |
31712 KB |
Output is correct |
71 |
Correct |
114 ms |
34172 KB |
Output is correct |
72 |
Correct |
461 ms |
37252 KB |
Output is correct |
73 |
Correct |
846 ms |
52576 KB |
Output is correct |
74 |
Correct |
876 ms |
52444 KB |
Output is correct |
75 |
Correct |
875 ms |
52572 KB |
Output is correct |
76 |
Correct |
876 ms |
52444 KB |
Output is correct |
77 |
Correct |
869 ms |
52316 KB |
Output is correct |
78 |
Correct |
852 ms |
52444 KB |
Output is correct |
79 |
Correct |
873 ms |
52320 KB |
Output is correct |
80 |
Correct |
858 ms |
52316 KB |
Output is correct |
81 |
Correct |
878 ms |
52572 KB |
Output is correct |
82 |
Correct |
866 ms |
52700 KB |
Output is correct |
83 |
Correct |
881 ms |
52304 KB |
Output is correct |
84 |
Correct |
857 ms |
52192 KB |
Output is correct |
85 |
Correct |
874 ms |
52320 KB |
Output is correct |
86 |
Correct |
887 ms |
52316 KB |
Output is correct |
87 |
Correct |
865 ms |
52444 KB |
Output is correct |
88 |
Correct |
849 ms |
52240 KB |
Output is correct |
89 |
Correct |
323 ms |
36324 KB |
Output is correct |
90 |
Correct |
868 ms |
52320 KB |
Output is correct |
91 |
Correct |
743 ms |
53052 KB |
Output is correct |
92 |
Correct |
252 ms |
33120 KB |
Output is correct |
93 |
Correct |
302 ms |
33272 KB |
Output is correct |
94 |
Correct |
243 ms |
33144 KB |
Output is correct |
95 |
Correct |
244 ms |
32864 KB |
Output is correct |
96 |
Correct |
344 ms |
32580 KB |
Output is correct |
97 |
Correct |
335 ms |
35136 KB |
Output is correct |
98 |
Correct |
259 ms |
32736 KB |
Output is correct |
99 |
Correct |
333 ms |
36836 KB |
Output is correct |
100 |
Correct |
251 ms |
32888 KB |
Output is correct |