#include <bits/stdc++.h>
#define int int64_t
#define ii pair<int,int>
#define x first
#define y second
#define vi vector<int>
#define vvi vector<vi>
#define vii vector<ii>
#define vvii vector<vii>
#define vb vector<bool>
#define vvb vector<vb>
#define pb push_back
#define loop(i,s,e) for(int i=(s);i<(e);i++)
#define loopr(i,s,e) for(int i=(e)-1;i>=(s);i--)
#define chkmax(a,b) a = max(a,b)
#define chkmin(a,b) a=min(a,b)
#define all(x) x.begin(),x.end()
using namespace std;
const int INF = 2e18, MOD = 1e9 + 7;
int n,m;
vvii g;
vi dijkstra(int s){
priority_queue<ii> q; q.push({0,s});
vi d(n, INF); d[s] = 0;
while(q.size()){
int cur = q.top().y, dd = -q.top().x; q.pop();
if (d[cur]!=dd) continue;
for(auto nei:g[cur]){
int v = dd + nei.y;
if (v < d[nei.x]){
d[nei.x] = v;
q.push({-d[nei.x], nei.x});
}
}
}
return d;
}
int32_t main(){
cin>>n>>m;
int s,t; cin>>s>>t; s--, t--;
int u,v; cin>>u>>v; u--, v--;
g.resize(n);
loop(i,0,m){
int a,b,c; cin>>a>>b>>c;
a--,b--;
g[a].pb({b,c});
g[b].pb({a,c});
}
vi ds = dijkstra(s), dt = dijkstra(t);
vi du = dijkstra(u), dv = dijkstra(v);
vb good(n);
int d = ds[t];
loop(i,0,n){
int v = ds[i] + dt[i];
if (v == d) good[i] = 1;
}
vvi ag(n);
vi deg(n);
loop(i,0,n) if(good[i]){
for(auto nei:g[i]) if(good[nei.x]){
int v = ds[i] + nei.y;
if (v == ds[nei.x]){
ag[nei.x].pb(i);
deg[i]++;
}
}
}
queue<int> q;
loop(i,0,n) if(deg[i]==0) q.push(i);
vi bestu(n, INF), bestv(n, INF);
int ans = du[v];
while(q.size()){
int cur = q.front(); q.pop();
// cout<<"CUR: "<<cur+1<<endl;
chkmin(ans, bestu[cur] + dv[cur]);
chkmin(ans, bestv[cur] + du[cur]);
chkmin(bestu[cur], du[cur]);
chkmin(bestv[cur], dv[cur]);
for(int nei:ag[cur]) {
chkmin(bestu[nei], bestu[cur]);
chkmin(bestv[nei], bestv[cur]);
if (--deg[nei]==0) q.push(nei);
}
}
cout<<ans<<endl;
return 0;
}
/*
color a
cls
g++ code.cpp -o code & code
6 6
1 6
1 4
1 2 1
2 3 1
3 5 1
2 4 3
4 5 2
5 6 1
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
538 ms |
25636 KB |
Output is correct |
2 |
Correct |
506 ms |
25232 KB |
Output is correct |
3 |
Correct |
551 ms |
26336 KB |
Output is correct |
4 |
Correct |
519 ms |
25520 KB |
Output is correct |
5 |
Correct |
541 ms |
25612 KB |
Output is correct |
6 |
Correct |
517 ms |
25592 KB |
Output is correct |
7 |
Correct |
530 ms |
25964 KB |
Output is correct |
8 |
Correct |
577 ms |
25796 KB |
Output is correct |
9 |
Correct |
514 ms |
26124 KB |
Output is correct |
10 |
Correct |
492 ms |
26340 KB |
Output is correct |
11 |
Correct |
285 ms |
19308 KB |
Output is correct |
12 |
Correct |
605 ms |
25952 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
534 ms |
25672 KB |
Output is correct |
2 |
Correct |
546 ms |
25404 KB |
Output is correct |
3 |
Correct |
506 ms |
25080 KB |
Output is correct |
4 |
Correct |
546 ms |
25328 KB |
Output is correct |
5 |
Correct |
520 ms |
25504 KB |
Output is correct |
6 |
Correct |
546 ms |
26088 KB |
Output is correct |
7 |
Correct |
570 ms |
26092 KB |
Output is correct |
8 |
Correct |
536 ms |
25336 KB |
Output is correct |
9 |
Correct |
516 ms |
25332 KB |
Output is correct |
10 |
Correct |
542 ms |
25204 KB |
Output is correct |
11 |
Correct |
263 ms |
19948 KB |
Output is correct |
12 |
Correct |
527 ms |
26292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
2156 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
42 ms |
3820 KB |
Output is correct |
5 |
Correct |
21 ms |
2028 KB |
Output is correct |
6 |
Correct |
3 ms |
492 KB |
Output is correct |
7 |
Correct |
3 ms |
492 KB |
Output is correct |
8 |
Correct |
4 ms |
620 KB |
Output is correct |
9 |
Correct |
2 ms |
492 KB |
Output is correct |
10 |
Correct |
21 ms |
2028 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
2 ms |
364 KB |
Output is correct |
15 |
Correct |
2 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
538 ms |
25636 KB |
Output is correct |
2 |
Correct |
506 ms |
25232 KB |
Output is correct |
3 |
Correct |
551 ms |
26336 KB |
Output is correct |
4 |
Correct |
519 ms |
25520 KB |
Output is correct |
5 |
Correct |
541 ms |
25612 KB |
Output is correct |
6 |
Correct |
517 ms |
25592 KB |
Output is correct |
7 |
Correct |
530 ms |
25964 KB |
Output is correct |
8 |
Correct |
577 ms |
25796 KB |
Output is correct |
9 |
Correct |
514 ms |
26124 KB |
Output is correct |
10 |
Correct |
492 ms |
26340 KB |
Output is correct |
11 |
Correct |
285 ms |
19308 KB |
Output is correct |
12 |
Correct |
605 ms |
25952 KB |
Output is correct |
13 |
Correct |
534 ms |
25672 KB |
Output is correct |
14 |
Correct |
546 ms |
25404 KB |
Output is correct |
15 |
Correct |
506 ms |
25080 KB |
Output is correct |
16 |
Correct |
546 ms |
25328 KB |
Output is correct |
17 |
Correct |
520 ms |
25504 KB |
Output is correct |
18 |
Correct |
546 ms |
26088 KB |
Output is correct |
19 |
Correct |
570 ms |
26092 KB |
Output is correct |
20 |
Correct |
536 ms |
25336 KB |
Output is correct |
21 |
Correct |
516 ms |
25332 KB |
Output is correct |
22 |
Correct |
542 ms |
25204 KB |
Output is correct |
23 |
Correct |
263 ms |
19948 KB |
Output is correct |
24 |
Correct |
527 ms |
26292 KB |
Output is correct |
25 |
Correct |
22 ms |
2156 KB |
Output is correct |
26 |
Correct |
1 ms |
364 KB |
Output is correct |
27 |
Correct |
1 ms |
364 KB |
Output is correct |
28 |
Correct |
42 ms |
3820 KB |
Output is correct |
29 |
Correct |
21 ms |
2028 KB |
Output is correct |
30 |
Correct |
3 ms |
492 KB |
Output is correct |
31 |
Correct |
3 ms |
492 KB |
Output is correct |
32 |
Correct |
4 ms |
620 KB |
Output is correct |
33 |
Correct |
2 ms |
492 KB |
Output is correct |
34 |
Correct |
21 ms |
2028 KB |
Output is correct |
35 |
Correct |
1 ms |
364 KB |
Output is correct |
36 |
Correct |
1 ms |
364 KB |
Output is correct |
37 |
Correct |
1 ms |
364 KB |
Output is correct |
38 |
Correct |
2 ms |
364 KB |
Output is correct |
39 |
Correct |
2 ms |
364 KB |
Output is correct |
40 |
Correct |
480 ms |
25044 KB |
Output is correct |
41 |
Correct |
534 ms |
25884 KB |
Output is correct |
42 |
Correct |
523 ms |
26128 KB |
Output is correct |
43 |
Correct |
279 ms |
20716 KB |
Output is correct |
44 |
Correct |
286 ms |
20716 KB |
Output is correct |
45 |
Correct |
552 ms |
27428 KB |
Output is correct |
46 |
Correct |
540 ms |
27044 KB |
Output is correct |
47 |
Correct |
502 ms |
25592 KB |
Output is correct |
48 |
Correct |
270 ms |
20076 KB |
Output is correct |
49 |
Correct |
453 ms |
24912 KB |
Output is correct |
50 |
Correct |
512 ms |
26620 KB |
Output is correct |
51 |
Correct |
523 ms |
27184 KB |
Output is correct |