#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<long long> vl;
typedef vector<int> vi;
int n, m, s1, e1, s2, e2;
const ll inf = 1e18;
vector<pii> G[100100];
vl dijkstra(int start){
vl dist(n);
for(int i = 0; i < n; i++) dist[i] = inf;
priority_queue<pll, vector<pll>, greater<pll>>q;
q.push({0, start});
dist[start] = 0;
while(!q.empty()){
pll x = q.top();
q.pop();
if(dist[x.second] < x.first) continue;
for(pii y : G[x.second]){
if(x.first + y.second < dist[y.first]){
dist[y.first] = x.first + y.second;
q.push({dist[y.first], y.first});
}
}
}
return dist;
}
ll pair1[2][100100], pair2[2][100100];
pair<ll,ll> st[100100];
bool ok[100100];
pll comb(pll a, pll b) {
return {min(a.first,b.first),min(a.second,b.second)};
}
int main(){
cin>>n>>m>>s1>>e1>>s2>>e2;
s1--;
e1--;
s2--;
e2--;
for(int i = 0; i < m; i++){
ll a, b, c;
cin>>a>>b>>c;
a--; b--;
G[a].pb(mp(b,c));
G[b].pb(mp(a,c));
}
// assert(false);
vl arr = dijkstra(s1);
for(int i = 0; i < n; i++) pair1[0][i] = arr[i];
arr = dijkstra(e1);
for(int i = 0; i < n; i++) pair1[1][i] = arr[i];
arr = dijkstra(s2);
for(int i = 0; i < n; i++) pair2[0][i] = arr[i];
arr = dijkstra(e2);
for(int i = 0; i < n; i++) pair2[1][i] = arr[i];
// assert(false);
for(int i = 0; i < n; i++) st[i] = {inf, inf};
ll ans = pair2[0][e2];
vector<pll> v;
memset(ok, false, sizeof ok);
for(int i = 0; i < n; i++){
if (pair1[0][i]+pair1[1][i] == pair1[0][e1]) {
ok[i] = 1;
v.pb({pair1[0][i],i});
}
}
sort(v.rbegin(),v.rend());
for (auto a: v) {
for (auto t: G[a.second]) if (ok[t.first]) st[a.second] = comb(st[a.second],st[t.first]);
ans = min(ans,min(st[a.second].first+pair2[1][a.second],st[a.second].second+pair2[0][a.second]));
st[a.second] = comb(st[a.second],{pair2[0][a.second],pair2[1][a.second]});
}
cout<<ans<<endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
347 ms |
15944 KB |
Output is correct |
2 |
Correct |
371 ms |
18892 KB |
Output is correct |
3 |
Correct |
384 ms |
21280 KB |
Output is correct |
4 |
Correct |
380 ms |
19652 KB |
Output is correct |
5 |
Correct |
329 ms |
19680 KB |
Output is correct |
6 |
Correct |
371 ms |
19908 KB |
Output is correct |
7 |
Correct |
354 ms |
19776 KB |
Output is correct |
8 |
Correct |
356 ms |
19760 KB |
Output is correct |
9 |
Correct |
371 ms |
19748 KB |
Output is correct |
10 |
Correct |
352 ms |
19816 KB |
Output is correct |
11 |
Correct |
190 ms |
15308 KB |
Output is correct |
12 |
Correct |
403 ms |
19572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
361 ms |
15376 KB |
Output is correct |
2 |
Correct |
355 ms |
18872 KB |
Output is correct |
3 |
Correct |
381 ms |
18812 KB |
Output is correct |
4 |
Correct |
351 ms |
18912 KB |
Output is correct |
5 |
Correct |
378 ms |
19504 KB |
Output is correct |
6 |
Correct |
357 ms |
20144 KB |
Output is correct |
7 |
Correct |
372 ms |
20952 KB |
Output is correct |
8 |
Correct |
357 ms |
18892 KB |
Output is correct |
9 |
Correct |
361 ms |
19500 KB |
Output is correct |
10 |
Correct |
367 ms |
18872 KB |
Output is correct |
11 |
Correct |
158 ms |
15660 KB |
Output is correct |
12 |
Correct |
341 ms |
20156 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
3500 KB |
Output is correct |
2 |
Correct |
2 ms |
2772 KB |
Output is correct |
3 |
Correct |
2 ms |
2792 KB |
Output is correct |
4 |
Correct |
34 ms |
4884 KB |
Output is correct |
5 |
Correct |
18 ms |
3764 KB |
Output is correct |
6 |
Correct |
3 ms |
2772 KB |
Output is correct |
7 |
Correct |
4 ms |
2900 KB |
Output is correct |
8 |
Correct |
5 ms |
2924 KB |
Output is correct |
9 |
Correct |
3 ms |
2772 KB |
Output is correct |
10 |
Correct |
19 ms |
3916 KB |
Output is correct |
11 |
Correct |
2 ms |
2796 KB |
Output is correct |
12 |
Correct |
2 ms |
2788 KB |
Output is correct |
13 |
Correct |
2 ms |
2800 KB |
Output is correct |
14 |
Correct |
3 ms |
2772 KB |
Output is correct |
15 |
Correct |
2 ms |
2796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
347 ms |
15944 KB |
Output is correct |
2 |
Correct |
371 ms |
18892 KB |
Output is correct |
3 |
Correct |
384 ms |
21280 KB |
Output is correct |
4 |
Correct |
380 ms |
19652 KB |
Output is correct |
5 |
Correct |
329 ms |
19680 KB |
Output is correct |
6 |
Correct |
371 ms |
19908 KB |
Output is correct |
7 |
Correct |
354 ms |
19776 KB |
Output is correct |
8 |
Correct |
356 ms |
19760 KB |
Output is correct |
9 |
Correct |
371 ms |
19748 KB |
Output is correct |
10 |
Correct |
352 ms |
19816 KB |
Output is correct |
11 |
Correct |
190 ms |
15308 KB |
Output is correct |
12 |
Correct |
403 ms |
19572 KB |
Output is correct |
13 |
Correct |
361 ms |
15376 KB |
Output is correct |
14 |
Correct |
355 ms |
18872 KB |
Output is correct |
15 |
Correct |
381 ms |
18812 KB |
Output is correct |
16 |
Correct |
351 ms |
18912 KB |
Output is correct |
17 |
Correct |
378 ms |
19504 KB |
Output is correct |
18 |
Correct |
357 ms |
20144 KB |
Output is correct |
19 |
Correct |
372 ms |
20952 KB |
Output is correct |
20 |
Correct |
357 ms |
18892 KB |
Output is correct |
21 |
Correct |
361 ms |
19500 KB |
Output is correct |
22 |
Correct |
367 ms |
18872 KB |
Output is correct |
23 |
Correct |
158 ms |
15660 KB |
Output is correct |
24 |
Correct |
341 ms |
20156 KB |
Output is correct |
25 |
Correct |
19 ms |
3500 KB |
Output is correct |
26 |
Correct |
2 ms |
2772 KB |
Output is correct |
27 |
Correct |
2 ms |
2792 KB |
Output is correct |
28 |
Correct |
34 ms |
4884 KB |
Output is correct |
29 |
Correct |
18 ms |
3764 KB |
Output is correct |
30 |
Correct |
3 ms |
2772 KB |
Output is correct |
31 |
Correct |
4 ms |
2900 KB |
Output is correct |
32 |
Correct |
5 ms |
2924 KB |
Output is correct |
33 |
Correct |
3 ms |
2772 KB |
Output is correct |
34 |
Correct |
19 ms |
3916 KB |
Output is correct |
35 |
Correct |
2 ms |
2796 KB |
Output is correct |
36 |
Correct |
2 ms |
2788 KB |
Output is correct |
37 |
Correct |
2 ms |
2800 KB |
Output is correct |
38 |
Correct |
3 ms |
2772 KB |
Output is correct |
39 |
Correct |
2 ms |
2796 KB |
Output is correct |
40 |
Correct |
375 ms |
20340 KB |
Output is correct |
41 |
Correct |
397 ms |
19472 KB |
Output is correct |
42 |
Correct |
368 ms |
19608 KB |
Output is correct |
43 |
Correct |
171 ms |
16752 KB |
Output is correct |
44 |
Correct |
161 ms |
16760 KB |
Output is correct |
45 |
Correct |
386 ms |
20956 KB |
Output is correct |
46 |
Correct |
333 ms |
20632 KB |
Output is correct |
47 |
Correct |
392 ms |
19708 KB |
Output is correct |
48 |
Correct |
172 ms |
16300 KB |
Output is correct |
49 |
Correct |
321 ms |
19812 KB |
Output is correct |
50 |
Correct |
363 ms |
21084 KB |
Output is correct |
51 |
Correct |
336 ms |
20992 KB |
Output is correct |