#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <vector>
#include <bitset>
#include <queue>
#include <set>
typedef long long llong;
const int MAXN = 500000 + 10;
const int INF = 1e9;
int n, m, k, q;
int answer[MAXN];
struct DSU
{
struct Query
{
int u, v;
int idx;
};
int par[MAXN];
std::vector <Query> queries[MAXN];
void build()
{
std::iota(par + 1, par + 1 + n, 1);
}
int find(int node)
{
if (par[node] == node) return node;
return par[node] = find(par[node]);
}
void connect(int u, int v, int newMin)
{
u = find(u);
v = find(v);
if (u == v)
{
return;
}
if (queries[u].size() < queries[v].size())
{
std::swap(u, v);
}
par[v] = u;
for (const Query &curr : queries[v])
{
if (areConnected(curr.v, curr.u))
{
if (answer[curr.idx] == -1) answer[curr.idx] = newMin;
} else
{
queries[u].push_back(curr);
}
}
}
bool areConnected(int u, int v)
{
return find(u) == find(v);
}
};
DSU dsu;
int dist[MAXN];
int perm[MAXN];
std::vector <int> npp;
std::priority_queue <std::pair <int,int>> pq;
std::vector <std::pair <int,int>> g[MAXN];
bool vis[MAXN];
void solve()
{
std::fill(dist + 1, dist + 1 + n, INF);
for (int i = 0 ; i < k ; ++i)
{
dist[npp[i]] = 0;
pq.push({0, npp[i]});
}
while (!pq.empty())
{
auto [d, node] = pq.top();
pq.pop();
if (vis[node])
{
continue;
}
vis[node] = true;
for (const auto &[u, w] : g[node])
{
if (dist[u] > dist[node] + w)
{
dist[u] = dist[node] + w;
pq.push({-dist[u], u});
}
}
}
std::cin >> q;
dsu.build();
std::fill(answer + 1, answer + 1 + q, -1);
for (int i = 1 ; i <= q ; ++i)
{
int from, to;
std::cin >> from >> to;
dsu.queries[from].push_back({from, to, i});
dsu.queries[to].push_back({to, from, i});
}
std::iota(perm + 1, perm + 1 + n, 1);
std::sort(perm + 1, perm + 1 + n, [&](int x, int y)
{
return dist[x] > dist[y];
});
for (int i = 1 ; i <= n ; ++i)
{
for (const auto &[u, d] : g[perm[i]])
{
if (dist[perm[i]] <= dist[u])
{
dsu.connect(perm[i], u, dist[perm[i]]);
}
}
}
}
void print()
{
for (int i = 1 ; i <= q ; ++i)
{
std::cout << answer[i] << '\n';
}
}
void input()
{
std::cin >> n >> m;
for (int i = 1 ; i <= m ; ++i)
{
int u, v, d;
std::cin >> u >> v >> d;
g[u].push_back({v, d});
g[v].push_back({u, d});
}
std::cin >> k;
npp.resize(k);
for (int i = 0 ; i < k ; ++i)
{
std::cin >> npp[i];
// std::cout << "here: " << npp[i] << '\n';
}
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
int main()
{
fastIOI();
input();
solve();
print();
return 0;
}
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
31064 KB |
Output is correct |
2 |
Correct |
6 ms |
31324 KB |
Output is correct |
3 |
Correct |
7 ms |
31324 KB |
Output is correct |
4 |
Correct |
6 ms |
31068 KB |
Output is correct |
5 |
Correct |
7 ms |
31324 KB |
Output is correct |
6 |
Correct |
8 ms |
31320 KB |
Output is correct |
7 |
Correct |
6 ms |
31068 KB |
Output is correct |
8 |
Correct |
6 ms |
31068 KB |
Output is correct |
9 |
Correct |
7 ms |
31324 KB |
Output is correct |
10 |
Correct |
7 ms |
31360 KB |
Output is correct |
11 |
Correct |
7 ms |
31324 KB |
Output is correct |
12 |
Correct |
6 ms |
31296 KB |
Output is correct |
13 |
Correct |
7 ms |
31160 KB |
Output is correct |
14 |
Correct |
7 ms |
31576 KB |
Output is correct |
15 |
Correct |
7 ms |
31324 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
31064 KB |
Output is correct |
2 |
Correct |
6 ms |
31324 KB |
Output is correct |
3 |
Correct |
7 ms |
31324 KB |
Output is correct |
4 |
Correct |
6 ms |
31068 KB |
Output is correct |
5 |
Correct |
7 ms |
31324 KB |
Output is correct |
6 |
Correct |
8 ms |
31320 KB |
Output is correct |
7 |
Correct |
6 ms |
31068 KB |
Output is correct |
8 |
Correct |
6 ms |
31068 KB |
Output is correct |
9 |
Correct |
7 ms |
31324 KB |
Output is correct |
10 |
Correct |
7 ms |
31360 KB |
Output is correct |
11 |
Correct |
7 ms |
31324 KB |
Output is correct |
12 |
Correct |
6 ms |
31296 KB |
Output is correct |
13 |
Correct |
7 ms |
31160 KB |
Output is correct |
14 |
Correct |
7 ms |
31576 KB |
Output is correct |
15 |
Correct |
7 ms |
31324 KB |
Output is correct |
16 |
Correct |
98 ms |
43492 KB |
Output is correct |
17 |
Correct |
330 ms |
60872 KB |
Output is correct |
18 |
Correct |
28 ms |
34088 KB |
Output is correct |
19 |
Correct |
93 ms |
43496 KB |
Output is correct |
20 |
Correct |
296 ms |
60952 KB |
Output is correct |
21 |
Correct |
150 ms |
49272 KB |
Output is correct |
22 |
Correct |
77 ms |
41740 KB |
Output is correct |
23 |
Correct |
283 ms |
60752 KB |
Output is correct |
24 |
Correct |
272 ms |
60916 KB |
Output is correct |
25 |
Correct |
323 ms |
61048 KB |
Output is correct |
26 |
Correct |
96 ms |
43332 KB |
Output is correct |
27 |
Correct |
98 ms |
43304 KB |
Output is correct |
28 |
Correct |
101 ms |
43360 KB |
Output is correct |
29 |
Correct |
88 ms |
43496 KB |
Output is correct |
30 |
Correct |
89 ms |
43572 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
31068 KB |
Output is correct |
2 |
Correct |
6 ms |
31068 KB |
Output is correct |
3 |
Correct |
6 ms |
31196 KB |
Output is correct |
4 |
Correct |
6 ms |
31068 KB |
Output is correct |
5 |
Correct |
7 ms |
31068 KB |
Output is correct |
6 |
Correct |
6 ms |
31064 KB |
Output is correct |
7 |
Correct |
6 ms |
31068 KB |
Output is correct |
8 |
Correct |
6 ms |
31068 KB |
Output is correct |
9 |
Correct |
8 ms |
31068 KB |
Output is correct |
10 |
Correct |
6 ms |
31068 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
119 ms |
38376 KB |
Output is correct |
2 |
Correct |
231 ms |
46284 KB |
Output is correct |
3 |
Correct |
288 ms |
46364 KB |
Output is correct |
4 |
Correct |
44 ms |
34440 KB |
Output is correct |
5 |
Correct |
243 ms |
46424 KB |
Output is correct |
6 |
Correct |
223 ms |
46480 KB |
Output is correct |
7 |
Correct |
275 ms |
46376 KB |
Output is correct |
8 |
Correct |
241 ms |
46432 KB |
Output is correct |
9 |
Correct |
238 ms |
46360 KB |
Output is correct |
10 |
Correct |
226 ms |
46468 KB |
Output is correct |
11 |
Correct |
261 ms |
46300 KB |
Output is correct |
12 |
Correct |
278 ms |
46388 KB |
Output is correct |
13 |
Correct |
235 ms |
46592 KB |
Output is correct |
14 |
Correct |
250 ms |
46396 KB |
Output is correct |
15 |
Correct |
240 ms |
47452 KB |
Output is correct |
16 |
Correct |
295 ms |
46332 KB |
Output is correct |
17 |
Correct |
235 ms |
46544 KB |
Output is correct |
18 |
Correct |
234 ms |
46404 KB |
Output is correct |
19 |
Correct |
45 ms |
34444 KB |
Output is correct |
20 |
Correct |
248 ms |
46392 KB |
Output is correct |
21 |
Correct |
227 ms |
46792 KB |
Output is correct |
22 |
Correct |
58 ms |
36548 KB |
Output is correct |
23 |
Correct |
60 ms |
34968 KB |
Output is correct |
24 |
Correct |
69 ms |
36548 KB |
Output is correct |
25 |
Correct |
55 ms |
36556 KB |
Output is correct |
26 |
Correct |
60 ms |
34900 KB |
Output is correct |
27 |
Correct |
44 ms |
34452 KB |
Output is correct |
28 |
Correct |
57 ms |
36552 KB |
Output is correct |
29 |
Correct |
52 ms |
34544 KB |
Output is correct |
30 |
Correct |
54 ms |
36560 KB |
Output is correct |
31 |
Correct |
45 ms |
34392 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
31064 KB |
Output is correct |
2 |
Correct |
6 ms |
31324 KB |
Output is correct |
3 |
Correct |
7 ms |
31324 KB |
Output is correct |
4 |
Correct |
6 ms |
31068 KB |
Output is correct |
5 |
Correct |
7 ms |
31324 KB |
Output is correct |
6 |
Correct |
8 ms |
31320 KB |
Output is correct |
7 |
Correct |
6 ms |
31068 KB |
Output is correct |
8 |
Correct |
6 ms |
31068 KB |
Output is correct |
9 |
Correct |
7 ms |
31324 KB |
Output is correct |
10 |
Correct |
7 ms |
31360 KB |
Output is correct |
11 |
Correct |
7 ms |
31324 KB |
Output is correct |
12 |
Correct |
6 ms |
31296 KB |
Output is correct |
13 |
Correct |
7 ms |
31160 KB |
Output is correct |
14 |
Correct |
7 ms |
31576 KB |
Output is correct |
15 |
Correct |
7 ms |
31324 KB |
Output is correct |
16 |
Correct |
98 ms |
43492 KB |
Output is correct |
17 |
Correct |
330 ms |
60872 KB |
Output is correct |
18 |
Correct |
28 ms |
34088 KB |
Output is correct |
19 |
Correct |
93 ms |
43496 KB |
Output is correct |
20 |
Correct |
296 ms |
60952 KB |
Output is correct |
21 |
Correct |
150 ms |
49272 KB |
Output is correct |
22 |
Correct |
77 ms |
41740 KB |
Output is correct |
23 |
Correct |
283 ms |
60752 KB |
Output is correct |
24 |
Correct |
272 ms |
60916 KB |
Output is correct |
25 |
Correct |
323 ms |
61048 KB |
Output is correct |
26 |
Correct |
96 ms |
43332 KB |
Output is correct |
27 |
Correct |
98 ms |
43304 KB |
Output is correct |
28 |
Correct |
101 ms |
43360 KB |
Output is correct |
29 |
Correct |
88 ms |
43496 KB |
Output is correct |
30 |
Correct |
89 ms |
43572 KB |
Output is correct |
31 |
Correct |
6 ms |
31068 KB |
Output is correct |
32 |
Correct |
6 ms |
31068 KB |
Output is correct |
33 |
Correct |
6 ms |
31196 KB |
Output is correct |
34 |
Correct |
6 ms |
31068 KB |
Output is correct |
35 |
Correct |
7 ms |
31068 KB |
Output is correct |
36 |
Correct |
6 ms |
31064 KB |
Output is correct |
37 |
Correct |
6 ms |
31068 KB |
Output is correct |
38 |
Correct |
6 ms |
31068 KB |
Output is correct |
39 |
Correct |
8 ms |
31068 KB |
Output is correct |
40 |
Correct |
6 ms |
31068 KB |
Output is correct |
41 |
Correct |
119 ms |
38376 KB |
Output is correct |
42 |
Correct |
231 ms |
46284 KB |
Output is correct |
43 |
Correct |
288 ms |
46364 KB |
Output is correct |
44 |
Correct |
44 ms |
34440 KB |
Output is correct |
45 |
Correct |
243 ms |
46424 KB |
Output is correct |
46 |
Correct |
223 ms |
46480 KB |
Output is correct |
47 |
Correct |
275 ms |
46376 KB |
Output is correct |
48 |
Correct |
241 ms |
46432 KB |
Output is correct |
49 |
Correct |
238 ms |
46360 KB |
Output is correct |
50 |
Correct |
226 ms |
46468 KB |
Output is correct |
51 |
Correct |
261 ms |
46300 KB |
Output is correct |
52 |
Correct |
278 ms |
46388 KB |
Output is correct |
53 |
Correct |
235 ms |
46592 KB |
Output is correct |
54 |
Correct |
250 ms |
46396 KB |
Output is correct |
55 |
Correct |
240 ms |
47452 KB |
Output is correct |
56 |
Correct |
295 ms |
46332 KB |
Output is correct |
57 |
Correct |
235 ms |
46544 KB |
Output is correct |
58 |
Correct |
234 ms |
46404 KB |
Output is correct |
59 |
Correct |
45 ms |
34444 KB |
Output is correct |
60 |
Correct |
248 ms |
46392 KB |
Output is correct |
61 |
Correct |
227 ms |
46792 KB |
Output is correct |
62 |
Correct |
58 ms |
36548 KB |
Output is correct |
63 |
Correct |
60 ms |
34968 KB |
Output is correct |
64 |
Correct |
69 ms |
36548 KB |
Output is correct |
65 |
Correct |
55 ms |
36556 KB |
Output is correct |
66 |
Correct |
60 ms |
34900 KB |
Output is correct |
67 |
Correct |
44 ms |
34452 KB |
Output is correct |
68 |
Correct |
57 ms |
36552 KB |
Output is correct |
69 |
Correct |
52 ms |
34544 KB |
Output is correct |
70 |
Correct |
54 ms |
36560 KB |
Output is correct |
71 |
Correct |
45 ms |
34392 KB |
Output is correct |
72 |
Correct |
157 ms |
49036 KB |
Output is correct |
73 |
Correct |
337 ms |
60924 KB |
Output is correct |
74 |
Correct |
296 ms |
60868 KB |
Output is correct |
75 |
Correct |
303 ms |
61036 KB |
Output is correct |
76 |
Correct |
324 ms |
60912 KB |
Output is correct |
77 |
Correct |
304 ms |
61132 KB |
Output is correct |
78 |
Correct |
307 ms |
60824 KB |
Output is correct |
79 |
Correct |
299 ms |
61040 KB |
Output is correct |
80 |
Correct |
298 ms |
60932 KB |
Output is correct |
81 |
Correct |
291 ms |
60828 KB |
Output is correct |
82 |
Correct |
334 ms |
60852 KB |
Output is correct |
83 |
Correct |
275 ms |
61052 KB |
Output is correct |
84 |
Correct |
265 ms |
61152 KB |
Output is correct |
85 |
Correct |
301 ms |
61832 KB |
Output is correct |
86 |
Correct |
340 ms |
60840 KB |
Output is correct |
87 |
Correct |
300 ms |
60972 KB |
Output is correct |
88 |
Correct |
294 ms |
60864 KB |
Output is correct |
89 |
Correct |
97 ms |
43384 KB |
Output is correct |
90 |
Correct |
315 ms |
60868 KB |
Output is correct |
91 |
Correct |
269 ms |
61732 KB |
Output is correct |
92 |
Correct |
101 ms |
45128 KB |
Output is correct |
93 |
Correct |
119 ms |
52644 KB |
Output is correct |
94 |
Correct |
101 ms |
45132 KB |
Output is correct |
95 |
Correct |
107 ms |
45256 KB |
Output is correct |
96 |
Correct |
123 ms |
52708 KB |
Output is correct |
97 |
Correct |
101 ms |
43848 KB |
Output is correct |
98 |
Correct |
122 ms |
45104 KB |
Output is correct |
99 |
Correct |
108 ms |
43856 KB |
Output is correct |
100 |
Correct |
102 ms |
45104 KB |
Output is correct |