#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=1e5+5;
vector <pair <int,int> >g[N];
int ds[N],dv[N],du[N],vis[N],dpU[N],dpV[N];
int res=0;
void dfs(int v){
if(vis[v])return;
vis[v]=1;
dpU[v]=du[v];dpV[v]=dv[v];
for(auto to : g[v]){
if(ds[v]==ds[to.ff]+to.ss){
dfs(to.ff);
dpU[v]=min(dpU[v],dpU[to.ff]);
dpV[v]=min(dpV[v],dpV[to.ff]);
}
}
res=min(res,dpU[v]+dv[v]);
res=min(res,dpV[v]+du[v]);
}
signed main(){
int n,m,s,t,u,w;
cin>>n>>m>>s>>t>>u>>w;
for(int i=0;i<m;i++){
int a,b,c;
cin>>a>>b>>c;
g[a].pb({b,c});
g[b].pb({a,c});
}
set <pair <int,int> > st;
for(int i=1;i<=n;i++){
ds[i]=1e18;du[i]=1e18;dv[i]=1e18;
}
ds[s]=0;
st.insert({0,s});
while(!st.empty()){
int v=st.begin()->second;
st.erase(st.begin());
for(auto to : g[v]){
if(ds[to.ff]>ds[v]+to.ss){
st.erase({ds[to.ff],to.ff});
ds[to.ff]=ds[v]+to.ss;
st.insert({ds[to.ff],to.ff});
}
}
}
du[u]=0;
st.insert({0,u});
while(!st.empty()){
int v=st.begin()->second;
st.erase(st.begin());
for(auto to : g[v]){
if(du[to.ff]>du[v]+to.ss){
st.erase({du[to.ff],to.ff});
du[to.ff]=du[v]+to.ss;
st.insert({du[to.ff],to.ff});
}
}
}
dv[w]=0;
st.insert({0,w});
while(!st.empty()){
int v=st.begin()->second;
st.erase(st.begin());
for(auto to : g[v]){
if(dv[to.ff]>dv[v]+to.ss){
st.erase({dv[to.ff],to.ff});
dv[to.ff]=dv[v]+to.ss;
st.insert({dv[to.ff],to.ff});
}
}
}
res=du[w];
dfs(t);
cout<<res<<"\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
359 ms |
24476 KB |
Output is correct |
2 |
Correct |
333 ms |
23376 KB |
Output is correct |
3 |
Correct |
311 ms |
28388 KB |
Output is correct |
4 |
Correct |
332 ms |
22656 KB |
Output is correct |
5 |
Correct |
327 ms |
23344 KB |
Output is correct |
6 |
Correct |
378 ms |
22488 KB |
Output is correct |
7 |
Correct |
330 ms |
23376 KB |
Output is correct |
8 |
Correct |
323 ms |
23464 KB |
Output is correct |
9 |
Correct |
362 ms |
21972 KB |
Output is correct |
10 |
Correct |
268 ms |
22284 KB |
Output is correct |
11 |
Correct |
106 ms |
17804 KB |
Output is correct |
12 |
Correct |
367 ms |
23728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
339 ms |
25936 KB |
Output is correct |
2 |
Correct |
345 ms |
25420 KB |
Output is correct |
3 |
Correct |
328 ms |
24996 KB |
Output is correct |
4 |
Correct |
386 ms |
25408 KB |
Output is correct |
5 |
Correct |
354 ms |
25936 KB |
Output is correct |
6 |
Correct |
314 ms |
27984 KB |
Output is correct |
7 |
Correct |
350 ms |
28240 KB |
Output is correct |
8 |
Correct |
353 ms |
25524 KB |
Output is correct |
9 |
Correct |
319 ms |
25936 KB |
Output is correct |
10 |
Correct |
344 ms |
25188 KB |
Output is correct |
11 |
Correct |
114 ms |
19420 KB |
Output is correct |
12 |
Correct |
307 ms |
28420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
7004 KB |
Output is correct |
2 |
Correct |
2 ms |
5212 KB |
Output is correct |
3 |
Correct |
2 ms |
5212 KB |
Output is correct |
4 |
Correct |
28 ms |
8532 KB |
Output is correct |
5 |
Correct |
15 ms |
7004 KB |
Output is correct |
6 |
Correct |
2 ms |
5304 KB |
Output is correct |
7 |
Correct |
3 ms |
5212 KB |
Output is correct |
8 |
Correct |
4 ms |
5524 KB |
Output is correct |
9 |
Correct |
2 ms |
5212 KB |
Output is correct |
10 |
Correct |
15 ms |
7004 KB |
Output is correct |
11 |
Correct |
1 ms |
5212 KB |
Output is correct |
12 |
Correct |
1 ms |
5212 KB |
Output is correct |
13 |
Correct |
2 ms |
5212 KB |
Output is correct |
14 |
Correct |
2 ms |
5264 KB |
Output is correct |
15 |
Correct |
2 ms |
5212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
359 ms |
24476 KB |
Output is correct |
2 |
Correct |
333 ms |
23376 KB |
Output is correct |
3 |
Correct |
311 ms |
28388 KB |
Output is correct |
4 |
Correct |
332 ms |
22656 KB |
Output is correct |
5 |
Correct |
327 ms |
23344 KB |
Output is correct |
6 |
Correct |
378 ms |
22488 KB |
Output is correct |
7 |
Correct |
330 ms |
23376 KB |
Output is correct |
8 |
Correct |
323 ms |
23464 KB |
Output is correct |
9 |
Correct |
362 ms |
21972 KB |
Output is correct |
10 |
Correct |
268 ms |
22284 KB |
Output is correct |
11 |
Correct |
106 ms |
17804 KB |
Output is correct |
12 |
Correct |
367 ms |
23728 KB |
Output is correct |
13 |
Correct |
339 ms |
25936 KB |
Output is correct |
14 |
Correct |
345 ms |
25420 KB |
Output is correct |
15 |
Correct |
328 ms |
24996 KB |
Output is correct |
16 |
Correct |
386 ms |
25408 KB |
Output is correct |
17 |
Correct |
354 ms |
25936 KB |
Output is correct |
18 |
Correct |
314 ms |
27984 KB |
Output is correct |
19 |
Correct |
350 ms |
28240 KB |
Output is correct |
20 |
Correct |
353 ms |
25524 KB |
Output is correct |
21 |
Correct |
319 ms |
25936 KB |
Output is correct |
22 |
Correct |
344 ms |
25188 KB |
Output is correct |
23 |
Correct |
114 ms |
19420 KB |
Output is correct |
24 |
Correct |
307 ms |
28420 KB |
Output is correct |
25 |
Correct |
15 ms |
7004 KB |
Output is correct |
26 |
Correct |
2 ms |
5212 KB |
Output is correct |
27 |
Correct |
2 ms |
5212 KB |
Output is correct |
28 |
Correct |
28 ms |
8532 KB |
Output is correct |
29 |
Correct |
15 ms |
7004 KB |
Output is correct |
30 |
Correct |
2 ms |
5304 KB |
Output is correct |
31 |
Correct |
3 ms |
5212 KB |
Output is correct |
32 |
Correct |
4 ms |
5524 KB |
Output is correct |
33 |
Correct |
2 ms |
5212 KB |
Output is correct |
34 |
Correct |
15 ms |
7004 KB |
Output is correct |
35 |
Correct |
1 ms |
5212 KB |
Output is correct |
36 |
Correct |
1 ms |
5212 KB |
Output is correct |
37 |
Correct |
2 ms |
5212 KB |
Output is correct |
38 |
Correct |
2 ms |
5264 KB |
Output is correct |
39 |
Correct |
2 ms |
5212 KB |
Output is correct |
40 |
Correct |
415 ms |
24820 KB |
Output is correct |
41 |
Correct |
344 ms |
22036 KB |
Output is correct |
42 |
Correct |
400 ms |
24116 KB |
Output is correct |
43 |
Correct |
127 ms |
18516 KB |
Output is correct |
44 |
Correct |
171 ms |
18528 KB |
Output is correct |
45 |
Correct |
472 ms |
22988 KB |
Output is correct |
46 |
Correct |
310 ms |
22588 KB |
Output is correct |
47 |
Correct |
337 ms |
23288 KB |
Output is correct |
48 |
Correct |
138 ms |
15564 KB |
Output is correct |
49 |
Correct |
285 ms |
24444 KB |
Output is correct |
50 |
Correct |
264 ms |
23032 KB |
Output is correct |
51 |
Correct |
276 ms |
22864 KB |
Output is correct |