#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<long long> vl;
int n, m;
vector<pii> G[100100];
ll dist[100100];
pair<int, ll> p[100100];
struct DSU{
vector<pair<int, ll>> p;
vi sz;
void init(int n){
for(int i = 0; i < n; i++){
p.pb({i,0});
sz.pb(1);
}
}
int get_size(int v){
return sz[v];
}
ll get_path(int v){
return p[v].second;
}
int find_parent(int v){
while(v != p[v].first)
v = p[v].first;
return v;
}
int get_parent(int v){
return p[v].first;
}
void merge(int a, int b, ll v)
{
a = find_parent(a);
b = find_parent(b);
if(a != b){
if(sz[a] > sz[b]) swap(a,b);
p[a].first = b;
p[a].second = v;
sz[b] += sz[a];
}
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(int i = 0; i < m; i++){
int a, b, w;
cin>>a>>b>>w;
a--; b--;
G[a].pb({b,w});
G[b].pb({a,w});
}
for(int i = 0; i < n; i++) dist[i] = 1e18;
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
int k;
cin>>k;
for(int i = 0; i < k; i++){
int g; cin>>g;
g--;
dist[g] = 0;
pq.push(mp(dist[g], g));
}
while(pq.size()){
pair<ll,int> cur= pq.top();
pq.pop();
if(cur.first!=dist[cur.second]) continue;
for(auto e : G[cur.second]){
if(dist[e.first]>dist[cur.second]+e.second){
dist[e.first] = dist[cur.second]+e.second;
pq.push({dist[e.first],e.first});
}
}
}
DSU dsu;
dsu.init(n);
vi order(n);
for(int i = 0; i < n; i++) order[i] = i;
sort(order.begin(),order.end(),[&](const int a,const int b){return dist[a]>dist[b];});
for(auto i : order){
for(auto e : G[i]){
if(dist[e.first]<dist[i] || (dist[e.first]==dist[i] && e.first<i)) continue;
dsu.merge(i,e.first,dist[i]);
}
}
int q;
cin>>q;
while(q--){
int s, t; cin>>s>>t;
s--; t--;
ll ans = 1e18;
while(s != t){
if(dsu.get_size(s) > dsu.get_size(t)) swap(s,t);
ans = min(ans, dsu.get_path(s));
s = dsu.get_parent(s);
}
cout<<ans<<"\n";
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2736 KB |
Output is correct |
3 |
Correct |
2 ms |
2772 KB |
Output is correct |
4 |
Correct |
1 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2772 KB |
Output is correct |
6 |
Correct |
2 ms |
2772 KB |
Output is correct |
7 |
Correct |
1 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2656 KB |
Output is correct |
9 |
Correct |
2 ms |
2772 KB |
Output is correct |
10 |
Correct |
2 ms |
2772 KB |
Output is correct |
11 |
Correct |
2 ms |
2772 KB |
Output is correct |
12 |
Correct |
2 ms |
2772 KB |
Output is correct |
13 |
Correct |
2 ms |
2772 KB |
Output is correct |
14 |
Correct |
2 ms |
2696 KB |
Output is correct |
15 |
Correct |
2 ms |
2772 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2736 KB |
Output is correct |
3 |
Correct |
2 ms |
2772 KB |
Output is correct |
4 |
Correct |
1 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2772 KB |
Output is correct |
6 |
Correct |
2 ms |
2772 KB |
Output is correct |
7 |
Correct |
1 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2656 KB |
Output is correct |
9 |
Correct |
2 ms |
2772 KB |
Output is correct |
10 |
Correct |
2 ms |
2772 KB |
Output is correct |
11 |
Correct |
2 ms |
2772 KB |
Output is correct |
12 |
Correct |
2 ms |
2772 KB |
Output is correct |
13 |
Correct |
2 ms |
2772 KB |
Output is correct |
14 |
Correct |
2 ms |
2696 KB |
Output is correct |
15 |
Correct |
2 ms |
2772 KB |
Output is correct |
16 |
Correct |
73 ms |
12448 KB |
Output is correct |
17 |
Correct |
235 ms |
32828 KB |
Output is correct |
18 |
Correct |
18 ms |
5336 KB |
Output is correct |
19 |
Correct |
67 ms |
15844 KB |
Output is correct |
20 |
Correct |
246 ms |
32828 KB |
Output is correct |
21 |
Correct |
118 ms |
19564 KB |
Output is correct |
22 |
Correct |
67 ms |
12772 KB |
Output is correct |
23 |
Correct |
235 ms |
32732 KB |
Output is correct |
24 |
Correct |
263 ms |
33068 KB |
Output is correct |
25 |
Correct |
244 ms |
32792 KB |
Output is correct |
26 |
Correct |
69 ms |
15588 KB |
Output is correct |
27 |
Correct |
67 ms |
15660 KB |
Output is correct |
28 |
Correct |
74 ms |
15608 KB |
Output is correct |
29 |
Correct |
72 ms |
15720 KB |
Output is correct |
30 |
Correct |
70 ms |
15844 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
1 ms |
2684 KB |
Output is correct |
5 |
Correct |
1 ms |
2644 KB |
Output is correct |
6 |
Correct |
1 ms |
2644 KB |
Output is correct |
7 |
Correct |
1 ms |
2644 KB |
Output is correct |
8 |
Correct |
1 ms |
2680 KB |
Output is correct |
9 |
Correct |
1 ms |
2644 KB |
Output is correct |
10 |
Correct |
1 ms |
2644 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
104 ms |
17028 KB |
Output is correct |
2 |
Correct |
213 ms |
31156 KB |
Output is correct |
3 |
Correct |
234 ms |
31140 KB |
Output is correct |
4 |
Correct |
46 ms |
10716 KB |
Output is correct |
5 |
Correct |
211 ms |
31220 KB |
Output is correct |
6 |
Correct |
233 ms |
31208 KB |
Output is correct |
7 |
Correct |
241 ms |
31144 KB |
Output is correct |
8 |
Correct |
218 ms |
31228 KB |
Output is correct |
9 |
Correct |
213 ms |
31060 KB |
Output is correct |
10 |
Correct |
232 ms |
31100 KB |
Output is correct |
11 |
Correct |
220 ms |
31104 KB |
Output is correct |
12 |
Correct |
254 ms |
31180 KB |
Output is correct |
13 |
Correct |
244 ms |
31148 KB |
Output is correct |
14 |
Correct |
228 ms |
31248 KB |
Output is correct |
15 |
Correct |
215 ms |
31284 KB |
Output is correct |
16 |
Correct |
230 ms |
31212 KB |
Output is correct |
17 |
Correct |
221 ms |
31116 KB |
Output is correct |
18 |
Correct |
246 ms |
31224 KB |
Output is correct |
19 |
Correct |
47 ms |
10828 KB |
Output is correct |
20 |
Correct |
214 ms |
31080 KB |
Output is correct |
21 |
Correct |
198 ms |
31012 KB |
Output is correct |
22 |
Correct |
49 ms |
14160 KB |
Output is correct |
23 |
Correct |
47 ms |
11208 KB |
Output is correct |
24 |
Correct |
57 ms |
14204 KB |
Output is correct |
25 |
Correct |
48 ms |
14108 KB |
Output is correct |
26 |
Correct |
50 ms |
11392 KB |
Output is correct |
27 |
Correct |
38 ms |
10776 KB |
Output is correct |
28 |
Correct |
48 ms |
14148 KB |
Output is correct |
29 |
Correct |
39 ms |
10736 KB |
Output is correct |
30 |
Correct |
49 ms |
14204 KB |
Output is correct |
31 |
Correct |
38 ms |
10688 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2736 KB |
Output is correct |
3 |
Correct |
2 ms |
2772 KB |
Output is correct |
4 |
Correct |
1 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2772 KB |
Output is correct |
6 |
Correct |
2 ms |
2772 KB |
Output is correct |
7 |
Correct |
1 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2656 KB |
Output is correct |
9 |
Correct |
2 ms |
2772 KB |
Output is correct |
10 |
Correct |
2 ms |
2772 KB |
Output is correct |
11 |
Correct |
2 ms |
2772 KB |
Output is correct |
12 |
Correct |
2 ms |
2772 KB |
Output is correct |
13 |
Correct |
2 ms |
2772 KB |
Output is correct |
14 |
Correct |
2 ms |
2696 KB |
Output is correct |
15 |
Correct |
2 ms |
2772 KB |
Output is correct |
16 |
Correct |
73 ms |
12448 KB |
Output is correct |
17 |
Correct |
235 ms |
32828 KB |
Output is correct |
18 |
Correct |
18 ms |
5336 KB |
Output is correct |
19 |
Correct |
67 ms |
15844 KB |
Output is correct |
20 |
Correct |
246 ms |
32828 KB |
Output is correct |
21 |
Correct |
118 ms |
19564 KB |
Output is correct |
22 |
Correct |
67 ms |
12772 KB |
Output is correct |
23 |
Correct |
235 ms |
32732 KB |
Output is correct |
24 |
Correct |
263 ms |
33068 KB |
Output is correct |
25 |
Correct |
244 ms |
32792 KB |
Output is correct |
26 |
Correct |
69 ms |
15588 KB |
Output is correct |
27 |
Correct |
67 ms |
15660 KB |
Output is correct |
28 |
Correct |
74 ms |
15608 KB |
Output is correct |
29 |
Correct |
72 ms |
15720 KB |
Output is correct |
30 |
Correct |
70 ms |
15844 KB |
Output is correct |
31 |
Correct |
1 ms |
2644 KB |
Output is correct |
32 |
Correct |
1 ms |
2644 KB |
Output is correct |
33 |
Correct |
1 ms |
2644 KB |
Output is correct |
34 |
Correct |
1 ms |
2684 KB |
Output is correct |
35 |
Correct |
1 ms |
2644 KB |
Output is correct |
36 |
Correct |
1 ms |
2644 KB |
Output is correct |
37 |
Correct |
1 ms |
2644 KB |
Output is correct |
38 |
Correct |
1 ms |
2680 KB |
Output is correct |
39 |
Correct |
1 ms |
2644 KB |
Output is correct |
40 |
Correct |
1 ms |
2644 KB |
Output is correct |
41 |
Correct |
104 ms |
17028 KB |
Output is correct |
42 |
Correct |
213 ms |
31156 KB |
Output is correct |
43 |
Correct |
234 ms |
31140 KB |
Output is correct |
44 |
Correct |
46 ms |
10716 KB |
Output is correct |
45 |
Correct |
211 ms |
31220 KB |
Output is correct |
46 |
Correct |
233 ms |
31208 KB |
Output is correct |
47 |
Correct |
241 ms |
31144 KB |
Output is correct |
48 |
Correct |
218 ms |
31228 KB |
Output is correct |
49 |
Correct |
213 ms |
31060 KB |
Output is correct |
50 |
Correct |
232 ms |
31100 KB |
Output is correct |
51 |
Correct |
220 ms |
31104 KB |
Output is correct |
52 |
Correct |
254 ms |
31180 KB |
Output is correct |
53 |
Correct |
244 ms |
31148 KB |
Output is correct |
54 |
Correct |
228 ms |
31248 KB |
Output is correct |
55 |
Correct |
215 ms |
31284 KB |
Output is correct |
56 |
Correct |
230 ms |
31212 KB |
Output is correct |
57 |
Correct |
221 ms |
31116 KB |
Output is correct |
58 |
Correct |
246 ms |
31224 KB |
Output is correct |
59 |
Correct |
47 ms |
10828 KB |
Output is correct |
60 |
Correct |
214 ms |
31080 KB |
Output is correct |
61 |
Correct |
198 ms |
31012 KB |
Output is correct |
62 |
Correct |
49 ms |
14160 KB |
Output is correct |
63 |
Correct |
47 ms |
11208 KB |
Output is correct |
64 |
Correct |
57 ms |
14204 KB |
Output is correct |
65 |
Correct |
48 ms |
14108 KB |
Output is correct |
66 |
Correct |
50 ms |
11392 KB |
Output is correct |
67 |
Correct |
38 ms |
10776 KB |
Output is correct |
68 |
Correct |
48 ms |
14148 KB |
Output is correct |
69 |
Correct |
39 ms |
10736 KB |
Output is correct |
70 |
Correct |
49 ms |
14204 KB |
Output is correct |
71 |
Correct |
38 ms |
10688 KB |
Output is correct |
72 |
Correct |
119 ms |
18292 KB |
Output is correct |
73 |
Correct |
234 ms |
32808 KB |
Output is correct |
74 |
Correct |
231 ms |
32832 KB |
Output is correct |
75 |
Correct |
279 ms |
32816 KB |
Output is correct |
76 |
Correct |
254 ms |
32792 KB |
Output is correct |
77 |
Correct |
268 ms |
32768 KB |
Output is correct |
78 |
Correct |
334 ms |
32728 KB |
Output is correct |
79 |
Correct |
282 ms |
32776 KB |
Output is correct |
80 |
Correct |
258 ms |
32852 KB |
Output is correct |
81 |
Correct |
238 ms |
32820 KB |
Output is correct |
82 |
Correct |
252 ms |
32900 KB |
Output is correct |
83 |
Correct |
243 ms |
32780 KB |
Output is correct |
84 |
Correct |
307 ms |
32764 KB |
Output is correct |
85 |
Correct |
302 ms |
32920 KB |
Output is correct |
86 |
Correct |
303 ms |
32792 KB |
Output is correct |
87 |
Correct |
318 ms |
32768 KB |
Output is correct |
88 |
Correct |
295 ms |
32812 KB |
Output is correct |
89 |
Correct |
70 ms |
12804 KB |
Output is correct |
90 |
Correct |
267 ms |
32776 KB |
Output is correct |
91 |
Correct |
241 ms |
32444 KB |
Output is correct |
92 |
Correct |
71 ms |
15652 KB |
Output is correct |
93 |
Correct |
73 ms |
13136 KB |
Output is correct |
94 |
Correct |
79 ms |
15584 KB |
Output is correct |
95 |
Correct |
81 ms |
15728 KB |
Output is correct |
96 |
Correct |
76 ms |
12764 KB |
Output is correct |
97 |
Correct |
59 ms |
12472 KB |
Output is correct |
98 |
Correct |
67 ms |
15608 KB |
Output is correct |
99 |
Correct |
61 ms |
12436 KB |
Output is correct |
100 |
Correct |
84 ms |
15712 KB |
Output is correct |