#include <bits/stdc++.h>
#define W while
#define int long long
using namespace std;
#define mp make_pair
const int N = 200005;
namespace SSSP {
struct edge {
int to,w;
edge *nex;
}*head[N];
void add(int u,int v,int w) {
edge *cur=new edge;
cur->to=v;
cur->w=w;
cur->nex=head[u];
head[u]=cur;
}
int vis[N];
priority_queue<pair<int,int>> q;
void dij(int s,int d[],size_t size) {
memset(vis,0,sizeof(vis));
memset(d,0x2f,size);
d[s]=0;
q.push(mp(-d[s],s));
W(!q.empty()) {
int u=q.top().second;
q.pop();
if(vis[u]) continue ;
vis[u]=1;
for(edge *cur=head[u]; cur; cur=cur->nex) {
if(d[cur->to]>d[u]+cur->w) {
d[cur->to]=d[u]+cur->w;
q.push(mp(-d[cur->to],cur->to));
}
}
}
}
} using namespace SSSP;
void chmin(int &x,int y) {
x=min(x,y);
}
int du[N],dv[N],dt[N],ans;
namespace SSSP_EX {
int d[N],fu[N],fv[N];
priority_queue<pair<int,int>> q;
void dp(int s) {
memset(vis,0,sizeof(vis));
memset(d,0x2f,sizeof(d));
memset(fu,0x2f,sizeof(fu));
memset(fv,0x2f,sizeof(fv));
d[s]=0,fu[s]=du[s],ans=fu[s]+dv[s];
q.push(mp(-d[s],s));
fv[s]=dv[s];
W(!q.empty()) {
int u=q.top().second;
q.pop();
if(vis[u]) continue ;
vis[u]=1;
for(edge *cur=head[u]; cur; cur=cur->nex) {
if(d[cur->to]>d[u]+cur->w) {
fu[cur->to]=fv[cur->to]=0x2f2f2f2f2f2f2f2f;
d[cur->to]=d[u]+cur->w;
q.push(mp(-d[cur->to],cur->to));
}
if(d[cur->to]==d[u]+cur->w) {
chmin(fu[cur->to],du[cur->to]);
chmin(fu[cur->to],fu[u]);
chmin(fv[cur->to],dv[cur->to]);
chmin(fv[cur->to],fv[u]);
}
}
}
}
} using namespace SSSP_EX;
signed main() {
//7338696
ios::sync_with_stdio(0),cin.tie(0);
int n,m,s,t,u,v,i;
int x,y,z;
cin>>n>>m>>s>>t>>u>>v;
for(i=1; i<=m; i++) {
cin>>x>>y>>z;
add(x,y,z);
add(y,x,z);
}
dij(u,du,sizeof du);
dij(t,dt,sizeof dt);
dij(v,dv,sizeof dv);
dp(s);
for(i=1; i<=n; i++) if(dt[s]==dt[i]+d[i]) chmin(ans,fu[i]+dv[i]);
for(i=1; i<=n; i++) {
if(dt[s]==dt[i]+d[i])
chmin(ans,fv[i]+du[i]);
}
chmin(ans,du[v]);
cout<<ans<<endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
319 ms |
32548 KB |
Output is correct |
2 |
Correct |
321 ms |
30528 KB |
Output is correct |
3 |
Correct |
333 ms |
31100 KB |
Output is correct |
4 |
Correct |
326 ms |
31488 KB |
Output is correct |
5 |
Correct |
331 ms |
30276 KB |
Output is correct |
6 |
Correct |
332 ms |
32648 KB |
Output is correct |
7 |
Correct |
342 ms |
30428 KB |
Output is correct |
8 |
Correct |
303 ms |
30484 KB |
Output is correct |
9 |
Correct |
331 ms |
31168 KB |
Output is correct |
10 |
Correct |
300 ms |
31164 KB |
Output is correct |
11 |
Correct |
91 ms |
20300 KB |
Output is correct |
12 |
Correct |
329 ms |
31064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
330 ms |
30780 KB |
Output is correct |
2 |
Correct |
335 ms |
30400 KB |
Output is correct |
3 |
Correct |
335 ms |
30400 KB |
Output is correct |
4 |
Correct |
354 ms |
30364 KB |
Output is correct |
5 |
Correct |
347 ms |
30544 KB |
Output is correct |
6 |
Correct |
335 ms |
30736 KB |
Output is correct |
7 |
Correct |
317 ms |
30420 KB |
Output is correct |
8 |
Correct |
329 ms |
30368 KB |
Output is correct |
9 |
Correct |
338 ms |
30376 KB |
Output is correct |
10 |
Correct |
335 ms |
30364 KB |
Output is correct |
11 |
Correct |
95 ms |
20428 KB |
Output is correct |
12 |
Correct |
293 ms |
30820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
13020 KB |
Output is correct |
2 |
Correct |
6 ms |
11272 KB |
Output is correct |
3 |
Correct |
5 ms |
11348 KB |
Output is correct |
4 |
Correct |
27 ms |
14828 KB |
Output is correct |
5 |
Correct |
15 ms |
12988 KB |
Output is correct |
6 |
Correct |
6 ms |
11348 KB |
Output is correct |
7 |
Correct |
6 ms |
11476 KB |
Output is correct |
8 |
Correct |
6 ms |
11476 KB |
Output is correct |
9 |
Correct |
6 ms |
11348 KB |
Output is correct |
10 |
Correct |
14 ms |
13016 KB |
Output is correct |
11 |
Correct |
5 ms |
11224 KB |
Output is correct |
12 |
Correct |
5 ms |
11220 KB |
Output is correct |
13 |
Correct |
5 ms |
11220 KB |
Output is correct |
14 |
Correct |
6 ms |
11360 KB |
Output is correct |
15 |
Correct |
5 ms |
11348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
319 ms |
32548 KB |
Output is correct |
2 |
Correct |
321 ms |
30528 KB |
Output is correct |
3 |
Correct |
333 ms |
31100 KB |
Output is correct |
4 |
Correct |
326 ms |
31488 KB |
Output is correct |
5 |
Correct |
331 ms |
30276 KB |
Output is correct |
6 |
Correct |
332 ms |
32648 KB |
Output is correct |
7 |
Correct |
342 ms |
30428 KB |
Output is correct |
8 |
Correct |
303 ms |
30484 KB |
Output is correct |
9 |
Correct |
331 ms |
31168 KB |
Output is correct |
10 |
Correct |
300 ms |
31164 KB |
Output is correct |
11 |
Correct |
91 ms |
20300 KB |
Output is correct |
12 |
Correct |
329 ms |
31064 KB |
Output is correct |
13 |
Correct |
330 ms |
30780 KB |
Output is correct |
14 |
Correct |
335 ms |
30400 KB |
Output is correct |
15 |
Correct |
335 ms |
30400 KB |
Output is correct |
16 |
Correct |
354 ms |
30364 KB |
Output is correct |
17 |
Correct |
347 ms |
30544 KB |
Output is correct |
18 |
Correct |
335 ms |
30736 KB |
Output is correct |
19 |
Correct |
317 ms |
30420 KB |
Output is correct |
20 |
Correct |
329 ms |
30368 KB |
Output is correct |
21 |
Correct |
338 ms |
30376 KB |
Output is correct |
22 |
Correct |
335 ms |
30364 KB |
Output is correct |
23 |
Correct |
95 ms |
20428 KB |
Output is correct |
24 |
Correct |
293 ms |
30820 KB |
Output is correct |
25 |
Correct |
14 ms |
13020 KB |
Output is correct |
26 |
Correct |
6 ms |
11272 KB |
Output is correct |
27 |
Correct |
5 ms |
11348 KB |
Output is correct |
28 |
Correct |
27 ms |
14828 KB |
Output is correct |
29 |
Correct |
15 ms |
12988 KB |
Output is correct |
30 |
Correct |
6 ms |
11348 KB |
Output is correct |
31 |
Correct |
6 ms |
11476 KB |
Output is correct |
32 |
Correct |
6 ms |
11476 KB |
Output is correct |
33 |
Correct |
6 ms |
11348 KB |
Output is correct |
34 |
Correct |
14 ms |
13016 KB |
Output is correct |
35 |
Correct |
5 ms |
11224 KB |
Output is correct |
36 |
Correct |
5 ms |
11220 KB |
Output is correct |
37 |
Correct |
5 ms |
11220 KB |
Output is correct |
38 |
Correct |
6 ms |
11360 KB |
Output is correct |
39 |
Correct |
5 ms |
11348 KB |
Output is correct |
40 |
Correct |
283 ms |
33376 KB |
Output is correct |
41 |
Correct |
309 ms |
31168 KB |
Output is correct |
42 |
Correct |
305 ms |
31176 KB |
Output is correct |
43 |
Correct |
91 ms |
20444 KB |
Output is correct |
44 |
Correct |
86 ms |
20348 KB |
Output is correct |
45 |
Correct |
265 ms |
30096 KB |
Output is correct |
46 |
Correct |
263 ms |
29840 KB |
Output is correct |
47 |
Correct |
310 ms |
31292 KB |
Output is correct |
48 |
Correct |
94 ms |
19860 KB |
Output is correct |
49 |
Correct |
253 ms |
33008 KB |
Output is correct |
50 |
Correct |
268 ms |
30116 KB |
Output is correct |
51 |
Correct |
254 ms |
30012 KB |
Output is correct |