#include <bits/stdc++.h>
using namespace std;
#define pii pair<long long,long long>
#define pb push_back
#define ppi pair<pii , pii>
#define piii pair<long long,ppi >
#define F first
#define S second
long long f1[100005] , f2[100005] , f3[100005] ;
int n , m ;
vector<pii> adj[100005];
int s, t , u , v;
int main(){
cin>>n>>m;
cin>>s>>t>>u>>v;
for(int i = 0 ; i < m ; i ++){
int x , y , z;
cin>>x>>y>>z;
adj[x].pb(pii(z,y));
adj[y].pb(pii(z,x));
}
for(int i = 1 ; i <= n; i++){
f1[i] = (long long) 1e18 , f2[i] = (long long) 1e18 , f3[i] = (long long) 1e18;
}
priority_queue<pii , vector<pii> , greater<pii> > pq;
pq.push(pii(0 , u));
while(!pq.empty()){
pii u = pq.top();
pq.pop();
if(u.F >= f1[u.S]) continue;
f1[u.S] = u.F;
for(auto p : adj[u.S]){
if(f1[p.S] > p.F + u.F){
pq.push(pii(p.F + u.F , p.S));
}
}
}
pq.push(pii(0 , v));
while(!pq.empty()){
pii u = pq.top();
pq.pop();
if(u.F >= f2[u.S]) continue;
f2[u.S] = u.F;
for(auto p : adj[u.S]){
if(f2[p.S] > p.F + u.F){
pq.push(pii(p.F + u.F , p.S));
}
}
}
long long ans = f2[u];
priority_queue< piii , vector<piii> , greater<piii> > pqq;
pqq.push(piii(0 , ppi(pii(f1[s] + f2[s] , s) , pii(f1[s] , f2[s]))));
while(!pqq.empty()){
piii u = pqq.top();
pqq.pop();
if(f3[u.S.F.S] <= u.F) continue;
if(u.S.F.S == t){
ans = min(ans , u.S.F.F);
break;
}
f3[u.S.F.S] = u.F;
for(auto p : adj[u.S.F.S]){
if(f3[p.S] > u.F + p.F){
pii w = u.S.S;
w.F = min(w.F , f1[p.S]) , w.S = min(w.S , f2[p.S]);
pqq.push(piii(u.F + p.F , ppi(pii(w.F + w.S, p.S) , w )));
}
}
}
cout<<ans<<endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
518 ms |
27648 KB |
Output is correct |
2 |
Correct |
490 ms |
31040 KB |
Output is correct |
3 |
Correct |
548 ms |
34256 KB |
Output is correct |
4 |
Correct |
563 ms |
38708 KB |
Output is correct |
5 |
Correct |
505 ms |
41724 KB |
Output is correct |
6 |
Correct |
544 ms |
46128 KB |
Output is correct |
7 |
Correct |
537 ms |
49240 KB |
Output is correct |
8 |
Correct |
512 ms |
52908 KB |
Output is correct |
9 |
Correct |
512 ms |
54592 KB |
Output is correct |
10 |
Correct |
527 ms |
61564 KB |
Output is correct |
11 |
Correct |
199 ms |
61564 KB |
Output is correct |
12 |
Correct |
579 ms |
68032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
507 ms |
71548 KB |
Output is correct |
2 |
Correct |
540 ms |
72452 KB |
Output is correct |
3 |
Correct |
482 ms |
75740 KB |
Output is correct |
4 |
Correct |
515 ms |
79340 KB |
Output is correct |
5 |
Correct |
543 ms |
82904 KB |
Output is correct |
6 |
Correct |
539 ms |
88844 KB |
Output is correct |
7 |
Correct |
511 ms |
89864 KB |
Output is correct |
8 |
Correct |
478 ms |
93284 KB |
Output is correct |
9 |
Correct |
549 ms |
96764 KB |
Output is correct |
10 |
Correct |
545 ms |
100248 KB |
Output is correct |
11 |
Correct |
219 ms |
100248 KB |
Output is correct |
12 |
Correct |
555 ms |
108540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
108540 KB |
Output is correct |
2 |
Correct |
4 ms |
108540 KB |
Output is correct |
3 |
Correct |
4 ms |
108540 KB |
Output is correct |
4 |
Correct |
75 ms |
108540 KB |
Output is correct |
5 |
Correct |
34 ms |
108540 KB |
Output is correct |
6 |
Correct |
5 ms |
108540 KB |
Output is correct |
7 |
Correct |
7 ms |
108540 KB |
Output is correct |
8 |
Correct |
8 ms |
108540 KB |
Output is correct |
9 |
Correct |
5 ms |
108540 KB |
Output is correct |
10 |
Correct |
38 ms |
108540 KB |
Output is correct |
11 |
Correct |
3 ms |
108540 KB |
Output is correct |
12 |
Correct |
5 ms |
108540 KB |
Output is correct |
13 |
Correct |
4 ms |
108540 KB |
Output is correct |
14 |
Correct |
5 ms |
108540 KB |
Output is correct |
15 |
Correct |
5 ms |
108540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
518 ms |
27648 KB |
Output is correct |
2 |
Correct |
490 ms |
31040 KB |
Output is correct |
3 |
Correct |
548 ms |
34256 KB |
Output is correct |
4 |
Correct |
563 ms |
38708 KB |
Output is correct |
5 |
Correct |
505 ms |
41724 KB |
Output is correct |
6 |
Correct |
544 ms |
46128 KB |
Output is correct |
7 |
Correct |
537 ms |
49240 KB |
Output is correct |
8 |
Correct |
512 ms |
52908 KB |
Output is correct |
9 |
Correct |
512 ms |
54592 KB |
Output is correct |
10 |
Correct |
527 ms |
61564 KB |
Output is correct |
11 |
Correct |
199 ms |
61564 KB |
Output is correct |
12 |
Correct |
579 ms |
68032 KB |
Output is correct |
13 |
Correct |
507 ms |
71548 KB |
Output is correct |
14 |
Correct |
540 ms |
72452 KB |
Output is correct |
15 |
Correct |
482 ms |
75740 KB |
Output is correct |
16 |
Correct |
515 ms |
79340 KB |
Output is correct |
17 |
Correct |
543 ms |
82904 KB |
Output is correct |
18 |
Correct |
539 ms |
88844 KB |
Output is correct |
19 |
Correct |
511 ms |
89864 KB |
Output is correct |
20 |
Correct |
478 ms |
93284 KB |
Output is correct |
21 |
Correct |
549 ms |
96764 KB |
Output is correct |
22 |
Correct |
545 ms |
100248 KB |
Output is correct |
23 |
Correct |
219 ms |
100248 KB |
Output is correct |
24 |
Correct |
555 ms |
108540 KB |
Output is correct |
25 |
Correct |
36 ms |
108540 KB |
Output is correct |
26 |
Correct |
4 ms |
108540 KB |
Output is correct |
27 |
Correct |
4 ms |
108540 KB |
Output is correct |
28 |
Correct |
75 ms |
108540 KB |
Output is correct |
29 |
Correct |
34 ms |
108540 KB |
Output is correct |
30 |
Correct |
5 ms |
108540 KB |
Output is correct |
31 |
Correct |
7 ms |
108540 KB |
Output is correct |
32 |
Correct |
8 ms |
108540 KB |
Output is correct |
33 |
Correct |
5 ms |
108540 KB |
Output is correct |
34 |
Correct |
38 ms |
108540 KB |
Output is correct |
35 |
Correct |
3 ms |
108540 KB |
Output is correct |
36 |
Correct |
5 ms |
108540 KB |
Output is correct |
37 |
Correct |
4 ms |
108540 KB |
Output is correct |
38 |
Correct |
5 ms |
108540 KB |
Output is correct |
39 |
Correct |
5 ms |
108540 KB |
Output is correct |
40 |
Correct |
537 ms |
114884 KB |
Output is correct |
41 |
Correct |
485 ms |
114884 KB |
Output is correct |
42 |
Correct |
596 ms |
123720 KB |
Output is correct |
43 |
Correct |
218 ms |
123720 KB |
Output is correct |
44 |
Correct |
225 ms |
123720 KB |
Output is correct |
45 |
Correct |
593 ms |
127688 KB |
Output is correct |
46 |
Correct |
542 ms |
130732 KB |
Output is correct |
47 |
Correct |
599 ms |
138448 KB |
Output is correct |
48 |
Correct |
212 ms |
138448 KB |
Output is correct |
49 |
Correct |
535 ms |
143264 KB |
Output is correct |
50 |
Correct |
527 ms |
143688 KB |
Output is correct |
51 |
Correct |
581 ms |
146920 KB |
Output is correct |