#include <bits/stdc++.h>
using namespace std ;
const int MAX = 1e5 + 10 ;
int arr[MAX] ;
int n , m , k , q ;
vector< vector< pair<int , int> > >adj(MAX) ;
vector< pair<int , int> >queries[MAX] ;
int dist[MAX] ;
void dijkstra()
{
for(int i = 1 ; i <= n ; ++i)
dist[i] = 1e9 ;
priority_queue< pair<int , int> , vector< pair<int , int> > , greater< pair<int , int> > >q ;
for(int i = 0 ; i < k ; ++i)
dist[arr[i]] = 0 , q.push({0 , arr[i]}) ;
while(!q.empty())
{
pair<int , int>p = q.top() ;
q.pop() ;
int node = p.second , cost = p.first ;
if(dist[node] < cost)
continue ;
for(auto &child : adj[node])
{
int child2 = child.first ;
int cost2 = cost + child.second ;
if(cost2 < dist[child2])
{
dist[child2] = cost2 ;
q.push({cost2 , child2}) ;
}
}
}
}
vector<int>v[MAX] ;
int par[MAX] , sz[MAX] , ans[MAX] ;
void init()
{
for(int i = 1 ; i <= n ; ++i)
par[i] = i , sz[i] = 1 , v[i].push_back(i) ;
}
int root(int node)
{
if(par[node] == node)
return node ;
return (par[node] = root(par[node])) ;
}
void Union(int x , int y , int z)
{
int a = root(x) ;
int b = root(y) ;
if(a == b)
return ;
if(sz[a] < sz[b])
swap(a , b) ;
while(v[b].size())
{
int node = v[b].back() ;
for(auto &p : queries[node])
{
int node2 = p.first , idx = p.second ;
if(root(node2) == a)
ans[idx] = z ;
}
v[a].push_back(node) ;
v[b].pop_back() ;
}
par[b] = a ;
sz[a] += sz[b] ;
}
int main()
{
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
cin>>n>>m ;
for(int i = 0 ; i < m ; ++i)
{
int x , y , z ;
cin>>x>>y>>z ;
adj[x].emplace_back(y , z) ;
adj[y].emplace_back(x , z) ;
}
cin>>k ;
for(int i = 0 ; i < k ; ++i)
cin>>arr[i] ;
cin>>q ;
for(int i = 0 ; i < q ; ++i)
{
int x , y ;
cin>>x>>y ;
queries[x].emplace_back(y , i) ;
queries[y].emplace_back(x , i) ;
}
dijkstra() ;
vector< array<int , 3> >edges ;
for(int i = 1 ; i <= n ; ++i)
{
for(auto &child : adj[i])
{
if(child.first > i)
edges.push_back({min(dist[i] , dist[child.first]) , i , child.first}) ;
}
}
sort(edges.begin() , edges.end()) ;
reverse(edges.begin() , edges.end()) ;
init() ;
for(auto &a : edges)
{
int x = a[1] , y = a[2] , z = a[0] ;
Union(x , y , z) ;
}
for(int i = 0 ; i < q ; ++i)
cout<<ans[i]<<"\n" ;
return 0 ;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7380 KB |
Output is correct |
2 |
Correct |
4 ms |
7508 KB |
Output is correct |
3 |
Correct |
4 ms |
7508 KB |
Output is correct |
4 |
Correct |
4 ms |
7380 KB |
Output is correct |
5 |
Correct |
5 ms |
7508 KB |
Output is correct |
6 |
Correct |
4 ms |
7508 KB |
Output is correct |
7 |
Correct |
4 ms |
7380 KB |
Output is correct |
8 |
Correct |
4 ms |
7408 KB |
Output is correct |
9 |
Correct |
5 ms |
7508 KB |
Output is correct |
10 |
Correct |
5 ms |
7508 KB |
Output is correct |
11 |
Correct |
5 ms |
7520 KB |
Output is correct |
12 |
Correct |
5 ms |
7540 KB |
Output is correct |
13 |
Correct |
5 ms |
7508 KB |
Output is correct |
14 |
Correct |
5 ms |
7508 KB |
Output is correct |
15 |
Correct |
5 ms |
7584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7380 KB |
Output is correct |
2 |
Correct |
4 ms |
7508 KB |
Output is correct |
3 |
Correct |
4 ms |
7508 KB |
Output is correct |
4 |
Correct |
4 ms |
7380 KB |
Output is correct |
5 |
Correct |
5 ms |
7508 KB |
Output is correct |
6 |
Correct |
4 ms |
7508 KB |
Output is correct |
7 |
Correct |
4 ms |
7380 KB |
Output is correct |
8 |
Correct |
4 ms |
7408 KB |
Output is correct |
9 |
Correct |
5 ms |
7508 KB |
Output is correct |
10 |
Correct |
5 ms |
7508 KB |
Output is correct |
11 |
Correct |
5 ms |
7520 KB |
Output is correct |
12 |
Correct |
5 ms |
7540 KB |
Output is correct |
13 |
Correct |
5 ms |
7508 KB |
Output is correct |
14 |
Correct |
5 ms |
7508 KB |
Output is correct |
15 |
Correct |
5 ms |
7584 KB |
Output is correct |
16 |
Correct |
148 ms |
23120 KB |
Output is correct |
17 |
Correct |
442 ms |
44444 KB |
Output is correct |
18 |
Correct |
41 ms |
10732 KB |
Output is correct |
19 |
Correct |
112 ms |
25168 KB |
Output is correct |
20 |
Correct |
435 ms |
44540 KB |
Output is correct |
21 |
Correct |
230 ms |
29716 KB |
Output is correct |
22 |
Correct |
131 ms |
24160 KB |
Output is correct |
23 |
Correct |
471 ms |
44540 KB |
Output is correct |
24 |
Correct |
491 ms |
44440 KB |
Output is correct |
25 |
Correct |
449 ms |
44640 KB |
Output is correct |
26 |
Correct |
117 ms |
24980 KB |
Output is correct |
27 |
Correct |
117 ms |
25148 KB |
Output is correct |
28 |
Correct |
127 ms |
25008 KB |
Output is correct |
29 |
Correct |
119 ms |
25188 KB |
Output is correct |
30 |
Correct |
112 ms |
25168 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7400 KB |
Output is correct |
2 |
Correct |
5 ms |
7380 KB |
Output is correct |
3 |
Correct |
4 ms |
7396 KB |
Output is correct |
4 |
Correct |
4 ms |
7380 KB |
Output is correct |
5 |
Correct |
4 ms |
7380 KB |
Output is correct |
6 |
Correct |
4 ms |
7400 KB |
Output is correct |
7 |
Correct |
4 ms |
7380 KB |
Output is correct |
8 |
Correct |
4 ms |
7380 KB |
Output is correct |
9 |
Correct |
5 ms |
7400 KB |
Output is correct |
10 |
Correct |
4 ms |
7380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
162 ms |
24008 KB |
Output is correct |
2 |
Correct |
419 ms |
39180 KB |
Output is correct |
3 |
Correct |
420 ms |
39140 KB |
Output is correct |
4 |
Correct |
65 ms |
18756 KB |
Output is correct |
5 |
Correct |
383 ms |
39132 KB |
Output is correct |
6 |
Correct |
376 ms |
39136 KB |
Output is correct |
7 |
Correct |
381 ms |
39104 KB |
Output is correct |
8 |
Correct |
413 ms |
39112 KB |
Output is correct |
9 |
Correct |
377 ms |
39180 KB |
Output is correct |
10 |
Correct |
414 ms |
39128 KB |
Output is correct |
11 |
Correct |
389 ms |
39164 KB |
Output is correct |
12 |
Correct |
404 ms |
39112 KB |
Output is correct |
13 |
Correct |
403 ms |
39248 KB |
Output is correct |
14 |
Correct |
433 ms |
39264 KB |
Output is correct |
15 |
Correct |
388 ms |
39764 KB |
Output is correct |
16 |
Correct |
406 ms |
39192 KB |
Output is correct |
17 |
Correct |
411 ms |
39128 KB |
Output is correct |
18 |
Correct |
390 ms |
39188 KB |
Output is correct |
19 |
Correct |
75 ms |
18500 KB |
Output is correct |
20 |
Correct |
434 ms |
39192 KB |
Output is correct |
21 |
Correct |
349 ms |
39884 KB |
Output is correct |
22 |
Correct |
79 ms |
19236 KB |
Output is correct |
23 |
Correct |
133 ms |
20072 KB |
Output is correct |
24 |
Correct |
81 ms |
19292 KB |
Output is correct |
25 |
Correct |
75 ms |
19252 KB |
Output is correct |
26 |
Correct |
111 ms |
20852 KB |
Output is correct |
27 |
Correct |
118 ms |
18728 KB |
Output is correct |
28 |
Correct |
80 ms |
19244 KB |
Output is correct |
29 |
Correct |
73 ms |
18628 KB |
Output is correct |
30 |
Correct |
70 ms |
19320 KB |
Output is correct |
31 |
Correct |
73 ms |
18608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7380 KB |
Output is correct |
2 |
Correct |
4 ms |
7508 KB |
Output is correct |
3 |
Correct |
4 ms |
7508 KB |
Output is correct |
4 |
Correct |
4 ms |
7380 KB |
Output is correct |
5 |
Correct |
5 ms |
7508 KB |
Output is correct |
6 |
Correct |
4 ms |
7508 KB |
Output is correct |
7 |
Correct |
4 ms |
7380 KB |
Output is correct |
8 |
Correct |
4 ms |
7408 KB |
Output is correct |
9 |
Correct |
5 ms |
7508 KB |
Output is correct |
10 |
Correct |
5 ms |
7508 KB |
Output is correct |
11 |
Correct |
5 ms |
7520 KB |
Output is correct |
12 |
Correct |
5 ms |
7540 KB |
Output is correct |
13 |
Correct |
5 ms |
7508 KB |
Output is correct |
14 |
Correct |
5 ms |
7508 KB |
Output is correct |
15 |
Correct |
5 ms |
7584 KB |
Output is correct |
16 |
Correct |
148 ms |
23120 KB |
Output is correct |
17 |
Correct |
442 ms |
44444 KB |
Output is correct |
18 |
Correct |
41 ms |
10732 KB |
Output is correct |
19 |
Correct |
112 ms |
25168 KB |
Output is correct |
20 |
Correct |
435 ms |
44540 KB |
Output is correct |
21 |
Correct |
230 ms |
29716 KB |
Output is correct |
22 |
Correct |
131 ms |
24160 KB |
Output is correct |
23 |
Correct |
471 ms |
44540 KB |
Output is correct |
24 |
Correct |
491 ms |
44440 KB |
Output is correct |
25 |
Correct |
449 ms |
44640 KB |
Output is correct |
26 |
Correct |
117 ms |
24980 KB |
Output is correct |
27 |
Correct |
117 ms |
25148 KB |
Output is correct |
28 |
Correct |
127 ms |
25008 KB |
Output is correct |
29 |
Correct |
119 ms |
25188 KB |
Output is correct |
30 |
Correct |
112 ms |
25168 KB |
Output is correct |
31 |
Correct |
4 ms |
7400 KB |
Output is correct |
32 |
Correct |
5 ms |
7380 KB |
Output is correct |
33 |
Correct |
4 ms |
7396 KB |
Output is correct |
34 |
Correct |
4 ms |
7380 KB |
Output is correct |
35 |
Correct |
4 ms |
7380 KB |
Output is correct |
36 |
Correct |
4 ms |
7400 KB |
Output is correct |
37 |
Correct |
4 ms |
7380 KB |
Output is correct |
38 |
Correct |
4 ms |
7380 KB |
Output is correct |
39 |
Correct |
5 ms |
7400 KB |
Output is correct |
40 |
Correct |
4 ms |
7380 KB |
Output is correct |
41 |
Correct |
162 ms |
24008 KB |
Output is correct |
42 |
Correct |
419 ms |
39180 KB |
Output is correct |
43 |
Correct |
420 ms |
39140 KB |
Output is correct |
44 |
Correct |
65 ms |
18756 KB |
Output is correct |
45 |
Correct |
383 ms |
39132 KB |
Output is correct |
46 |
Correct |
376 ms |
39136 KB |
Output is correct |
47 |
Correct |
381 ms |
39104 KB |
Output is correct |
48 |
Correct |
413 ms |
39112 KB |
Output is correct |
49 |
Correct |
377 ms |
39180 KB |
Output is correct |
50 |
Correct |
414 ms |
39128 KB |
Output is correct |
51 |
Correct |
389 ms |
39164 KB |
Output is correct |
52 |
Correct |
404 ms |
39112 KB |
Output is correct |
53 |
Correct |
403 ms |
39248 KB |
Output is correct |
54 |
Correct |
433 ms |
39264 KB |
Output is correct |
55 |
Correct |
388 ms |
39764 KB |
Output is correct |
56 |
Correct |
406 ms |
39192 KB |
Output is correct |
57 |
Correct |
411 ms |
39128 KB |
Output is correct |
58 |
Correct |
390 ms |
39188 KB |
Output is correct |
59 |
Correct |
75 ms |
18500 KB |
Output is correct |
60 |
Correct |
434 ms |
39192 KB |
Output is correct |
61 |
Correct |
349 ms |
39884 KB |
Output is correct |
62 |
Correct |
79 ms |
19236 KB |
Output is correct |
63 |
Correct |
133 ms |
20072 KB |
Output is correct |
64 |
Correct |
81 ms |
19292 KB |
Output is correct |
65 |
Correct |
75 ms |
19252 KB |
Output is correct |
66 |
Correct |
111 ms |
20852 KB |
Output is correct |
67 |
Correct |
118 ms |
18728 KB |
Output is correct |
68 |
Correct |
80 ms |
19244 KB |
Output is correct |
69 |
Correct |
73 ms |
18628 KB |
Output is correct |
70 |
Correct |
70 ms |
19320 KB |
Output is correct |
71 |
Correct |
73 ms |
18608 KB |
Output is correct |
72 |
Correct |
275 ms |
29460 KB |
Output is correct |
73 |
Correct |
449 ms |
44408 KB |
Output is correct |
74 |
Correct |
470 ms |
44532 KB |
Output is correct |
75 |
Correct |
467 ms |
44512 KB |
Output is correct |
76 |
Correct |
449 ms |
44500 KB |
Output is correct |
77 |
Correct |
449 ms |
44464 KB |
Output is correct |
78 |
Correct |
531 ms |
44480 KB |
Output is correct |
79 |
Correct |
434 ms |
44408 KB |
Output is correct |
80 |
Correct |
473 ms |
44584 KB |
Output is correct |
81 |
Correct |
437 ms |
44464 KB |
Output is correct |
82 |
Correct |
473 ms |
44396 KB |
Output is correct |
83 |
Correct |
483 ms |
44504 KB |
Output is correct |
84 |
Correct |
497 ms |
44440 KB |
Output is correct |
85 |
Correct |
484 ms |
44536 KB |
Output is correct |
86 |
Correct |
453 ms |
44460 KB |
Output is correct |
87 |
Correct |
516 ms |
44452 KB |
Output is correct |
88 |
Correct |
471 ms |
44484 KB |
Output is correct |
89 |
Correct |
143 ms |
24380 KB |
Output is correct |
90 |
Correct |
449 ms |
44412 KB |
Output is correct |
91 |
Correct |
468 ms |
45028 KB |
Output is correct |
92 |
Correct |
123 ms |
24600 KB |
Output is correct |
93 |
Correct |
170 ms |
25856 KB |
Output is correct |
94 |
Correct |
128 ms |
24488 KB |
Output is correct |
95 |
Correct |
117 ms |
24652 KB |
Output is correct |
96 |
Correct |
200 ms |
26228 KB |
Output is correct |
97 |
Correct |
139 ms |
24456 KB |
Output is correct |
98 |
Correct |
150 ms |
24512 KB |
Output is correct |
99 |
Correct |
144 ms |
24288 KB |
Output is correct |
100 |
Correct |
119 ms |
24564 KB |
Output is correct |