#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 100010, inf = 1e9;
vector<pair<int,int>> edge[MAX_N], allq[MAX_N];
template<class T> void join (vector<T> &a, vector<T> &b) { if (a.size() < b.size()) swap(a, b); a.insert(end(a), AI(b)); b.clear(); }
int dis[MAX_N], res[MAX_N];
bool vis[MAX_N];
int n, m, q;
struct dsu {
vector<int> g;
vector<vector<tuple<int,int,int>>> qry;
dsu(int n) {
g.resize(n+1); iota(AI(g), 0);
qry.resize(n+1);
for (int i = 1;i <= n;++i) {
for (auto [b, id] : allq[i])
qry[i].pb(i, b, id);
}
}
int F(int i) { return i == g[i] ? i : g[i] = F(g[i]); }
void M(int a, int b, int cost) {
a = F(a), b = F(b);
if (a == b) return;
if (qry[a].size() < qry[b].size()) swap(a, b);
g[b] = a;
for (auto [v, u, ind] : qry[b]) {
if (res[ind]) continue;
if (F(v) == F(u))
res[ind] = cost;
else
qry[a].pb(v, u, ind);
}
qry[b].clear();
}
};
int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
for (int a, b, w, i = 0;i < m;++i) {
cin >> a >> b >> w;
edge[a].pb(b, w), edge[b].pb(a, w);
}
fill(dis, dis + 1 + n, inf);
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
auto upd = [&](int x, int d) {
if (chmin(dis[x], d))
pq.emplace(d, x);
};
int k;
cin >> k;
for (int x, i = 0;i < k;++i) {
cin >> x ;
upd(x, 0);
}
cin >> q;
for (int s, t, i = 0;i < q;++i) {
cin >> s >> t;
allq[s].pb(t, i);
allq[t].pb(s, i);
}
while (pq.size()) {
auto [d, x] = pq.top(); pq.pop();
if (vis[x]) continue; vis[x] = true;
for (auto [u, w] : edge[x])
upd(u, w + d);
}
vector<int> od(n); iota(AI(od), 1);
sort(AI(od), [&](int x, int y) {
return dis[x] > dis[y];
});
dsu D(n + 10);
for (int x : od) {
DE(x, dis[x]);
for (auto [u, _] : edge[x])
if (dis[u] >= dis[x]) {
DE(x, u);
D.M(x, u, dis[x]);
}
}
for (int i = 0;i < q;++i)
cout << res[i] << '\n';
}
Compilation message
plan.cpp: In function 'int32_t main()':
plan.cpp:93:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
93 | if (vis[x]) continue; vis[x] = true;
| ^~
plan.cpp:93:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
93 | if (vis[x]) continue; vis[x] = true;
| ^~~
plan.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
plan.cpp:107:3: note: in expansion of macro 'DE'
107 | DE(x, dis[x]);
| ^~
plan.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
plan.cpp:110:5: note: in expansion of macro 'DE'
110 | DE(x, u);
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
5 ms |
5228 KB |
Output is correct |
3 |
Correct |
10 ms |
5228 KB |
Output is correct |
4 |
Correct |
4 ms |
5100 KB |
Output is correct |
5 |
Correct |
5 ms |
5228 KB |
Output is correct |
6 |
Correct |
5 ms |
5228 KB |
Output is correct |
7 |
Correct |
4 ms |
5100 KB |
Output is correct |
8 |
Correct |
8 ms |
5100 KB |
Output is correct |
9 |
Correct |
5 ms |
5228 KB |
Output is correct |
10 |
Correct |
11 ms |
5228 KB |
Output is correct |
11 |
Correct |
5 ms |
5228 KB |
Output is correct |
12 |
Correct |
10 ms |
5228 KB |
Output is correct |
13 |
Correct |
6 ms |
5228 KB |
Output is correct |
14 |
Correct |
5 ms |
5228 KB |
Output is correct |
15 |
Correct |
9 ms |
5248 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
5 ms |
5228 KB |
Output is correct |
3 |
Correct |
10 ms |
5228 KB |
Output is correct |
4 |
Correct |
4 ms |
5100 KB |
Output is correct |
5 |
Correct |
5 ms |
5228 KB |
Output is correct |
6 |
Correct |
5 ms |
5228 KB |
Output is correct |
7 |
Correct |
4 ms |
5100 KB |
Output is correct |
8 |
Correct |
8 ms |
5100 KB |
Output is correct |
9 |
Correct |
5 ms |
5228 KB |
Output is correct |
10 |
Correct |
11 ms |
5228 KB |
Output is correct |
11 |
Correct |
5 ms |
5228 KB |
Output is correct |
12 |
Correct |
10 ms |
5228 KB |
Output is correct |
13 |
Correct |
6 ms |
5228 KB |
Output is correct |
14 |
Correct |
5 ms |
5228 KB |
Output is correct |
15 |
Correct |
9 ms |
5248 KB |
Output is correct |
16 |
Correct |
212 ms |
20820 KB |
Output is correct |
17 |
Correct |
596 ms |
32424 KB |
Output is correct |
18 |
Correct |
35 ms |
7872 KB |
Output is correct |
19 |
Correct |
184 ms |
22360 KB |
Output is correct |
20 |
Correct |
605 ms |
32404 KB |
Output is correct |
21 |
Correct |
334 ms |
25528 KB |
Output is correct |
22 |
Correct |
197 ms |
19908 KB |
Output is correct |
23 |
Correct |
557 ms |
32652 KB |
Output is correct |
24 |
Correct |
565 ms |
32332 KB |
Output is correct |
25 |
Correct |
588 ms |
32356 KB |
Output is correct |
26 |
Correct |
175 ms |
22248 KB |
Output is correct |
27 |
Correct |
270 ms |
22232 KB |
Output is correct |
28 |
Correct |
189 ms |
22112 KB |
Output is correct |
29 |
Correct |
173 ms |
22232 KB |
Output is correct |
30 |
Correct |
337 ms |
22360 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
5100 KB |
Output is correct |
2 |
Correct |
4 ms |
5100 KB |
Output is correct |
3 |
Correct |
4 ms |
5100 KB |
Output is correct |
4 |
Correct |
4 ms |
5100 KB |
Output is correct |
5 |
Correct |
4 ms |
5100 KB |
Output is correct |
6 |
Correct |
7 ms |
5100 KB |
Output is correct |
7 |
Correct |
4 ms |
5100 KB |
Output is correct |
8 |
Correct |
4 ms |
5100 KB |
Output is correct |
9 |
Correct |
4 ms |
5100 KB |
Output is correct |
10 |
Correct |
7 ms |
5100 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
212 ms |
15712 KB |
Output is correct |
2 |
Correct |
461 ms |
23652 KB |
Output is correct |
3 |
Correct |
464 ms |
23652 KB |
Output is correct |
4 |
Correct |
86 ms |
11756 KB |
Output is correct |
5 |
Correct |
460 ms |
23908 KB |
Output is correct |
6 |
Correct |
423 ms |
23784 KB |
Output is correct |
7 |
Correct |
449 ms |
23776 KB |
Output is correct |
8 |
Correct |
418 ms |
23652 KB |
Output is correct |
9 |
Correct |
419 ms |
23652 KB |
Output is correct |
10 |
Correct |
425 ms |
23912 KB |
Output is correct |
11 |
Correct |
473 ms |
23780 KB |
Output is correct |
12 |
Correct |
425 ms |
23908 KB |
Output is correct |
13 |
Correct |
432 ms |
23780 KB |
Output is correct |
14 |
Correct |
444 ms |
23656 KB |
Output is correct |
15 |
Correct |
451 ms |
23776 KB |
Output is correct |
16 |
Correct |
453 ms |
23652 KB |
Output is correct |
17 |
Correct |
430 ms |
23780 KB |
Output is correct |
18 |
Correct |
452 ms |
23652 KB |
Output is correct |
19 |
Correct |
77 ms |
11884 KB |
Output is correct |
20 |
Correct |
453 ms |
23780 KB |
Output is correct |
21 |
Correct |
389 ms |
23396 KB |
Output is correct |
22 |
Correct |
101 ms |
13420 KB |
Output is correct |
23 |
Correct |
88 ms |
12268 KB |
Output is correct |
24 |
Correct |
98 ms |
13412 KB |
Output is correct |
25 |
Correct |
93 ms |
13412 KB |
Output is correct |
26 |
Correct |
105 ms |
12524 KB |
Output is correct |
27 |
Correct |
80 ms |
11756 KB |
Output is correct |
28 |
Correct |
98 ms |
13412 KB |
Output is correct |
29 |
Correct |
82 ms |
11756 KB |
Output is correct |
30 |
Correct |
98 ms |
13412 KB |
Output is correct |
31 |
Correct |
73 ms |
11756 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
5 ms |
5228 KB |
Output is correct |
3 |
Correct |
10 ms |
5228 KB |
Output is correct |
4 |
Correct |
4 ms |
5100 KB |
Output is correct |
5 |
Correct |
5 ms |
5228 KB |
Output is correct |
6 |
Correct |
5 ms |
5228 KB |
Output is correct |
7 |
Correct |
4 ms |
5100 KB |
Output is correct |
8 |
Correct |
8 ms |
5100 KB |
Output is correct |
9 |
Correct |
5 ms |
5228 KB |
Output is correct |
10 |
Correct |
11 ms |
5228 KB |
Output is correct |
11 |
Correct |
5 ms |
5228 KB |
Output is correct |
12 |
Correct |
10 ms |
5228 KB |
Output is correct |
13 |
Correct |
6 ms |
5228 KB |
Output is correct |
14 |
Correct |
5 ms |
5228 KB |
Output is correct |
15 |
Correct |
9 ms |
5248 KB |
Output is correct |
16 |
Correct |
212 ms |
20820 KB |
Output is correct |
17 |
Correct |
596 ms |
32424 KB |
Output is correct |
18 |
Correct |
35 ms |
7872 KB |
Output is correct |
19 |
Correct |
184 ms |
22360 KB |
Output is correct |
20 |
Correct |
605 ms |
32404 KB |
Output is correct |
21 |
Correct |
334 ms |
25528 KB |
Output is correct |
22 |
Correct |
197 ms |
19908 KB |
Output is correct |
23 |
Correct |
557 ms |
32652 KB |
Output is correct |
24 |
Correct |
565 ms |
32332 KB |
Output is correct |
25 |
Correct |
588 ms |
32356 KB |
Output is correct |
26 |
Correct |
175 ms |
22248 KB |
Output is correct |
27 |
Correct |
270 ms |
22232 KB |
Output is correct |
28 |
Correct |
189 ms |
22112 KB |
Output is correct |
29 |
Correct |
173 ms |
22232 KB |
Output is correct |
30 |
Correct |
337 ms |
22360 KB |
Output is correct |
31 |
Correct |
7 ms |
5100 KB |
Output is correct |
32 |
Correct |
4 ms |
5100 KB |
Output is correct |
33 |
Correct |
4 ms |
5100 KB |
Output is correct |
34 |
Correct |
4 ms |
5100 KB |
Output is correct |
35 |
Correct |
4 ms |
5100 KB |
Output is correct |
36 |
Correct |
7 ms |
5100 KB |
Output is correct |
37 |
Correct |
4 ms |
5100 KB |
Output is correct |
38 |
Correct |
4 ms |
5100 KB |
Output is correct |
39 |
Correct |
4 ms |
5100 KB |
Output is correct |
40 |
Correct |
7 ms |
5100 KB |
Output is correct |
41 |
Correct |
212 ms |
15712 KB |
Output is correct |
42 |
Correct |
461 ms |
23652 KB |
Output is correct |
43 |
Correct |
464 ms |
23652 KB |
Output is correct |
44 |
Correct |
86 ms |
11756 KB |
Output is correct |
45 |
Correct |
460 ms |
23908 KB |
Output is correct |
46 |
Correct |
423 ms |
23784 KB |
Output is correct |
47 |
Correct |
449 ms |
23776 KB |
Output is correct |
48 |
Correct |
418 ms |
23652 KB |
Output is correct |
49 |
Correct |
419 ms |
23652 KB |
Output is correct |
50 |
Correct |
425 ms |
23912 KB |
Output is correct |
51 |
Correct |
473 ms |
23780 KB |
Output is correct |
52 |
Correct |
425 ms |
23908 KB |
Output is correct |
53 |
Correct |
432 ms |
23780 KB |
Output is correct |
54 |
Correct |
444 ms |
23656 KB |
Output is correct |
55 |
Correct |
451 ms |
23776 KB |
Output is correct |
56 |
Correct |
453 ms |
23652 KB |
Output is correct |
57 |
Correct |
430 ms |
23780 KB |
Output is correct |
58 |
Correct |
452 ms |
23652 KB |
Output is correct |
59 |
Correct |
77 ms |
11884 KB |
Output is correct |
60 |
Correct |
453 ms |
23780 KB |
Output is correct |
61 |
Correct |
389 ms |
23396 KB |
Output is correct |
62 |
Correct |
101 ms |
13420 KB |
Output is correct |
63 |
Correct |
88 ms |
12268 KB |
Output is correct |
64 |
Correct |
98 ms |
13412 KB |
Output is correct |
65 |
Correct |
93 ms |
13412 KB |
Output is correct |
66 |
Correct |
105 ms |
12524 KB |
Output is correct |
67 |
Correct |
80 ms |
11756 KB |
Output is correct |
68 |
Correct |
98 ms |
13412 KB |
Output is correct |
69 |
Correct |
82 ms |
11756 KB |
Output is correct |
70 |
Correct |
98 ms |
13412 KB |
Output is correct |
71 |
Correct |
73 ms |
11756 KB |
Output is correct |
72 |
Correct |
320 ms |
25828 KB |
Output is correct |
73 |
Correct |
575 ms |
33096 KB |
Output is correct |
74 |
Correct |
548 ms |
32992 KB |
Output is correct |
75 |
Correct |
570 ms |
33120 KB |
Output is correct |
76 |
Correct |
543 ms |
32992 KB |
Output is correct |
77 |
Correct |
593 ms |
32988 KB |
Output is correct |
78 |
Correct |
558 ms |
32992 KB |
Output is correct |
79 |
Correct |
552 ms |
33036 KB |
Output is correct |
80 |
Correct |
570 ms |
32992 KB |
Output is correct |
81 |
Correct |
559 ms |
32968 KB |
Output is correct |
82 |
Correct |
545 ms |
33016 KB |
Output is correct |
83 |
Correct |
546 ms |
32992 KB |
Output is correct |
84 |
Correct |
576 ms |
33116 KB |
Output is correct |
85 |
Correct |
585 ms |
33888 KB |
Output is correct |
86 |
Correct |
556 ms |
32988 KB |
Output is correct |
87 |
Correct |
564 ms |
32988 KB |
Output is correct |
88 |
Correct |
551 ms |
33000 KB |
Output is correct |
89 |
Correct |
184 ms |
22500 KB |
Output is correct |
90 |
Correct |
553 ms |
32992 KB |
Output is correct |
91 |
Correct |
539 ms |
32684 KB |
Output is correct |
92 |
Correct |
198 ms |
24160 KB |
Output is correct |
93 |
Correct |
220 ms |
31392 KB |
Output is correct |
94 |
Correct |
204 ms |
24080 KB |
Output is correct |
95 |
Correct |
191 ms |
24036 KB |
Output is correct |
96 |
Correct |
250 ms |
31644 KB |
Output is correct |
97 |
Correct |
182 ms |
22620 KB |
Output is correct |
98 |
Correct |
216 ms |
24064 KB |
Output is correct |
99 |
Correct |
221 ms |
22844 KB |
Output is correct |
100 |
Correct |
214 ms |
24032 KB |
Output is correct |