#include <bits/stdc++.h>
#define int long long
#define ii pair<int, int>
#define iii pair<int,ii>
#define vii vector<ii>
#define fi first
#define se second
#define endl '\n'
using namespace std;
const double eps = 0.000001;
const int mod = 1000000007;
const int N = 100001;
const int MATRIX_SIZE = 3;
int n,m,s,t,u,v,du[N],dv[N],ds[N],dpu[N],dpv[N];
vector <ii> G[N];
bool vi[N];
void Dijk(int x,int *dist){
fill(dist+1,dist+n+1,1e18);
dist[x]=0;
priority_queue <ii,vector <ii>, greater <ii>> xet;
xet.push({0,x});
while (xet.size()){
ii tam=xet.top();
xet.pop();
if (tam.fi>dist[tam.se]) continue;
for (auto htc:G[tam.se]){
if (dist[htc.fi]>htc.se+tam.fi){
// cout<<htc.fi<<' '<<htc.se<<' '<<tam.fi<<endl;
dist[htc.fi]=htc.se+tam.fi;
xet.push({dist[htc.fi],htc.fi});
}
}
}
// dist[0]=2;
}
void Dp(){
fill(ds+1,ds+n+1,1e18);
ds[s]=0;
fill(dpu,dpu+n+1,1e18);
fill(dpv,dpv+n+1,1e18);
dpu[s]=du[s];
dpv[s]=dv[s];
priority_queue <iii,vector <iii>,greater<iii>> xet;
xet.push({0,{s,0}});
while (xet.size()){
iii tam=xet.top();
int dist=tam.fi;
int node=tam.se.fi;
int par=tam.se.se;
xet.pop();
if (dist>ds[node]) continue;
if (dpu[node]+dpv[node]>min(dpu[par],du[node])+min(dpv[par],dv[node])){
dpu[node]=min(dpu[par],du[node]);
dpv[node]=min(dpv[par],dv[node]);
}
// cout<<node<<' '<<dpu[node]<<' '<<dpv[node]<<' '<<par<<endl;
if (!vi[node]){
vi[node]=true;
for (auto x:G[node]){
if (ds[x.fi]>=x.se+dist){
ds[x.fi]=x.se+dist;
xet.push({ds[x.fi],{x.fi,node}});
}
}
}
}
}
void solve(){
cin>>n>>m>>s>>t>>u>>v;
for (int i=1,s1,s2,s3;i<=m;++i){
cin>>s1>>s2>>s3;
G[s2].push_back({s1,s3});
G[s1].push_back({s2,s3});
}
Dijk(u,du);
Dijk(v,dv);
// cout<<du[3];
// swap(t,s);
Dp();
cout<<min(dpu[t]+dpv[t],du[v]);
}
main() {
//freopen("ok.inp","r",stdin);
//freopen("ok.out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
}
Compilation message
commuter_pass.cpp:83:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
83 | main() {
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
163 ms |
25804 KB |
Output is correct |
2 |
Correct |
160 ms |
23452 KB |
Output is correct |
3 |
Correct |
170 ms |
23080 KB |
Output is correct |
4 |
Correct |
170 ms |
26176 KB |
Output is correct |
5 |
Correct |
159 ms |
23384 KB |
Output is correct |
6 |
Correct |
194 ms |
25808 KB |
Output is correct |
7 |
Correct |
173 ms |
23356 KB |
Output is correct |
8 |
Correct |
205 ms |
23588 KB |
Output is correct |
9 |
Correct |
214 ms |
23876 KB |
Output is correct |
10 |
Correct |
130 ms |
23940 KB |
Output is correct |
11 |
Correct |
50 ms |
14072 KB |
Output is correct |
12 |
Correct |
167 ms |
23804 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
173 ms |
24000 KB |
Output is correct |
2 |
Correct |
167 ms |
23432 KB |
Output is correct |
3 |
Correct |
190 ms |
23428 KB |
Output is correct |
4 |
Correct |
166 ms |
23460 KB |
Output is correct |
5 |
Correct |
165 ms |
23472 KB |
Output is correct |
6 |
Correct |
182 ms |
23292 KB |
Output is correct |
7 |
Correct |
167 ms |
23176 KB |
Output is correct |
8 |
Correct |
202 ms |
23556 KB |
Output is correct |
9 |
Correct |
197 ms |
23404 KB |
Output is correct |
10 |
Correct |
164 ms |
23440 KB |
Output is correct |
11 |
Correct |
47 ms |
14052 KB |
Output is correct |
12 |
Correct |
216 ms |
23060 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
8540 KB |
Output is correct |
2 |
Correct |
1 ms |
6748 KB |
Output is correct |
3 |
Correct |
1 ms |
6748 KB |
Output is correct |
4 |
Correct |
15 ms |
10620 KB |
Output is correct |
5 |
Correct |
6 ms |
8284 KB |
Output is correct |
6 |
Correct |
2 ms |
6744 KB |
Output is correct |
7 |
Correct |
3 ms |
6744 KB |
Output is correct |
8 |
Correct |
2 ms |
6748 KB |
Output is correct |
9 |
Correct |
2 ms |
6748 KB |
Output is correct |
10 |
Correct |
6 ms |
8448 KB |
Output is correct |
11 |
Correct |
1 ms |
6492 KB |
Output is correct |
12 |
Correct |
1 ms |
6492 KB |
Output is correct |
13 |
Correct |
1 ms |
6660 KB |
Output is correct |
14 |
Correct |
1 ms |
6748 KB |
Output is correct |
15 |
Correct |
2 ms |
6744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
163 ms |
25804 KB |
Output is correct |
2 |
Correct |
160 ms |
23452 KB |
Output is correct |
3 |
Correct |
170 ms |
23080 KB |
Output is correct |
4 |
Correct |
170 ms |
26176 KB |
Output is correct |
5 |
Correct |
159 ms |
23384 KB |
Output is correct |
6 |
Correct |
194 ms |
25808 KB |
Output is correct |
7 |
Correct |
173 ms |
23356 KB |
Output is correct |
8 |
Correct |
205 ms |
23588 KB |
Output is correct |
9 |
Correct |
214 ms |
23876 KB |
Output is correct |
10 |
Correct |
130 ms |
23940 KB |
Output is correct |
11 |
Correct |
50 ms |
14072 KB |
Output is correct |
12 |
Correct |
167 ms |
23804 KB |
Output is correct |
13 |
Correct |
173 ms |
24000 KB |
Output is correct |
14 |
Correct |
167 ms |
23432 KB |
Output is correct |
15 |
Correct |
190 ms |
23428 KB |
Output is correct |
16 |
Correct |
166 ms |
23460 KB |
Output is correct |
17 |
Correct |
165 ms |
23472 KB |
Output is correct |
18 |
Correct |
182 ms |
23292 KB |
Output is correct |
19 |
Correct |
167 ms |
23176 KB |
Output is correct |
20 |
Correct |
202 ms |
23556 KB |
Output is correct |
21 |
Correct |
197 ms |
23404 KB |
Output is correct |
22 |
Correct |
164 ms |
23440 KB |
Output is correct |
23 |
Correct |
47 ms |
14052 KB |
Output is correct |
24 |
Correct |
216 ms |
23060 KB |
Output is correct |
25 |
Correct |
7 ms |
8540 KB |
Output is correct |
26 |
Correct |
1 ms |
6748 KB |
Output is correct |
27 |
Correct |
1 ms |
6748 KB |
Output is correct |
28 |
Correct |
15 ms |
10620 KB |
Output is correct |
29 |
Correct |
6 ms |
8284 KB |
Output is correct |
30 |
Correct |
2 ms |
6744 KB |
Output is correct |
31 |
Correct |
3 ms |
6744 KB |
Output is correct |
32 |
Correct |
2 ms |
6748 KB |
Output is correct |
33 |
Correct |
2 ms |
6748 KB |
Output is correct |
34 |
Correct |
6 ms |
8448 KB |
Output is correct |
35 |
Correct |
1 ms |
6492 KB |
Output is correct |
36 |
Correct |
1 ms |
6492 KB |
Output is correct |
37 |
Correct |
1 ms |
6660 KB |
Output is correct |
38 |
Correct |
1 ms |
6748 KB |
Output is correct |
39 |
Correct |
2 ms |
6744 KB |
Output is correct |
40 |
Correct |
152 ms |
25824 KB |
Output is correct |
41 |
Correct |
154 ms |
23940 KB |
Output is correct |
42 |
Correct |
159 ms |
23972 KB |
Output is correct |
43 |
Correct |
52 ms |
13940 KB |
Output is correct |
44 |
Correct |
45 ms |
14160 KB |
Output is correct |
45 |
Correct |
150 ms |
23192 KB |
Output is correct |
46 |
Correct |
151 ms |
22852 KB |
Output is correct |
47 |
Correct |
176 ms |
25880 KB |
Output is correct |
48 |
Correct |
50 ms |
13396 KB |
Output is correct |
49 |
Correct |
151 ms |
25728 KB |
Output is correct |
50 |
Correct |
153 ms |
23156 KB |
Output is correct |
51 |
Correct |
145 ms |
23080 KB |
Output is correct |