#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef unsigned long long ll;
typedef pair<ll,int> pii;
const int MN=1e5+2;
int N,M,S,T,U,V;
ll du[MN],dv[MN],dis[MN],uU[MN],uV[MN],mU[MN],mV[MN],vU[MN],vV[MN];
bool vis[MN];
vector<pii> gr[MN];
int main() {
ios::sync_with_stdio(0);cin.tie(0);
cin>>N>>M>>S>>T>>U>>V;
for(int i=1;i<=M;++i) {
int u,v,w;
cin>>u>>v>>w;
gr[u].push_back(pii(w,v));
gr[v].push_back(pii(w,u));
}
fill(du+1,du+1+N,LLONG_MAX);
memset(vis,0,sizeof(vis));
priority_queue<pii,vector<pii>,greater<pii>> pq;
pq.push(pii(0,U));
du[U]=0;
while(!pq.empty()) {
int u=pq.top().s;
ll d=pq.top().f;
pq.pop();
if(vis[u]) continue;
vis[u]=1;
for(pii p:gr[u]) {
int v=p.s;
ll ed=p.f;
if(!vis[v]&&d+ed<du[v]) {
du[v]=d+ed;
pq.push(pii(du[v],v));
}
}
}
fill(dv+1,dv+1+N,LLONG_MAX);
memset(vis,0,sizeof(vis));
pq.push(pii(0,V));
dv[V]=0;
while(!pq.empty()) {
int u=pq.top().s;
ll d=pq.top().f;
pq.pop();
if(vis[u]) continue;
vis[u]=1;
for(pii p:gr[u]) {
int v=p.s;
ll ed=p.f;
if(!vis[v]&&d+ed<dv[v]) {
dv[v]=d+ed;
pq.push(pii(dv[v],v));
}
}
}
// S->T
fill(dis+1,dis+1+N,LLONG_MAX);
memset(vis,0,sizeof(vis));
pq.push(pii(0,S));
dis[S]=0;
uU[S]=vU[S]=mU[S]=du[S];
uV[S]=vV[S]=mV[S]=dv[S];
while(!pq.empty()) {
int x=pq.top().s;
ll d=pq.top().f;
pq.pop();
if(vis[x]) continue;
vis[x]=1;
for(pii p:gr[x]) {
int y=p.s;
ll ed=p.f;
if(!vis[y]) {
if(d+ed<dis[y]) {
dis[y]=d+ed;
pq.push(pii(dis[y],y));
uU[y]=min(uU[x],du[y]);
uV[y]=min(uV[x],dv[y]);
mU[y]=min(mU[x],du[y]);
mV[y]=min(mV[x],dv[y]);
vU[y]=min(vU[x],du[y]);
vV[y]=min(vV[x],dv[y]);
if(uU[y]+uV[y]<=mU[y]+mV[y]) {
mU[y]=uU[y];
mV[y]=uV[y];
}
if(vU[y]+vV[y]<=mU[y]+mV[y]) {
mU[y]=vU[y];
mV[y]=vV[y];
}
}
if(d+ed==dis[y]) {
if(uU[x]<uU[y]) {
uU[y]=uU[x];
uV[y]=uV[x];
}
if(vV[x]<vV[y]) {
vU[y]=vU[x];
vV[y]=vV[x];
}
if(mU[x]+mV[x]<mU[y]+mV[y]) {
mU[y]=mU[x];
mV[y]=mV[x];
}
mU[y]=min(mU[y],du[y]);
uU[y]=min(uU[y],du[y]);
vU[y]=min(vU[y],du[y]);
mV[y]=min(mV[y],dv[y]);
uV[y]=min(uV[y],dv[y]);
vV[y]=min(vV[y],dv[y]);
if(uU[y]+uV[y]<=mU[y]+mV[y]) {
mU[y]=uU[y];
mV[y]=uV[y];
}
if(vU[y]+vV[y]<=mU[y]+mV[y]) {
mU[y]=vU[y];
mV[y]=vV[y];
}
}
}
}
}
cout<<min(mU[T]+mV[T],du[V])<<'\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
272 ms |
21420 KB |
Output is correct |
2 |
Correct |
257 ms |
21196 KB |
Output is correct |
3 |
Correct |
263 ms |
20920 KB |
Output is correct |
4 |
Correct |
268 ms |
21392 KB |
Output is correct |
5 |
Correct |
237 ms |
21064 KB |
Output is correct |
6 |
Correct |
241 ms |
21480 KB |
Output is correct |
7 |
Correct |
263 ms |
21124 KB |
Output is correct |
8 |
Correct |
269 ms |
21160 KB |
Output is correct |
9 |
Correct |
270 ms |
21112 KB |
Output is correct |
10 |
Correct |
219 ms |
20872 KB |
Output is correct |
11 |
Correct |
120 ms |
14940 KB |
Output is correct |
12 |
Correct |
267 ms |
21028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
281 ms |
21396 KB |
Output is correct |
2 |
Correct |
296 ms |
21168 KB |
Output is correct |
3 |
Correct |
287 ms |
21112 KB |
Output is correct |
4 |
Correct |
292 ms |
21128 KB |
Output is correct |
5 |
Correct |
273 ms |
21196 KB |
Output is correct |
6 |
Correct |
266 ms |
21056 KB |
Output is correct |
7 |
Correct |
278 ms |
21068 KB |
Output is correct |
8 |
Correct |
275 ms |
21328 KB |
Output is correct |
9 |
Correct |
280 ms |
21112 KB |
Output is correct |
10 |
Correct |
279 ms |
21144 KB |
Output is correct |
11 |
Correct |
114 ms |
15004 KB |
Output is correct |
12 |
Correct |
264 ms |
21020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
4180 KB |
Output is correct |
2 |
Correct |
2 ms |
2772 KB |
Output is correct |
3 |
Correct |
2 ms |
2772 KB |
Output is correct |
4 |
Correct |
15 ms |
5588 KB |
Output is correct |
5 |
Correct |
8 ms |
4180 KB |
Output is correct |
6 |
Correct |
2 ms |
2900 KB |
Output is correct |
7 |
Correct |
3 ms |
2900 KB |
Output is correct |
8 |
Correct |
3 ms |
3028 KB |
Output is correct |
9 |
Correct |
2 ms |
2900 KB |
Output is correct |
10 |
Correct |
7 ms |
4180 KB |
Output is correct |
11 |
Correct |
2 ms |
2772 KB |
Output is correct |
12 |
Correct |
2 ms |
2772 KB |
Output is correct |
13 |
Correct |
2 ms |
2772 KB |
Output is correct |
14 |
Correct |
2 ms |
2772 KB |
Output is correct |
15 |
Correct |
2 ms |
2900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
272 ms |
21420 KB |
Output is correct |
2 |
Correct |
257 ms |
21196 KB |
Output is correct |
3 |
Correct |
263 ms |
20920 KB |
Output is correct |
4 |
Correct |
268 ms |
21392 KB |
Output is correct |
5 |
Correct |
237 ms |
21064 KB |
Output is correct |
6 |
Correct |
241 ms |
21480 KB |
Output is correct |
7 |
Correct |
263 ms |
21124 KB |
Output is correct |
8 |
Correct |
269 ms |
21160 KB |
Output is correct |
9 |
Correct |
270 ms |
21112 KB |
Output is correct |
10 |
Correct |
219 ms |
20872 KB |
Output is correct |
11 |
Correct |
120 ms |
14940 KB |
Output is correct |
12 |
Correct |
267 ms |
21028 KB |
Output is correct |
13 |
Correct |
281 ms |
21396 KB |
Output is correct |
14 |
Correct |
296 ms |
21168 KB |
Output is correct |
15 |
Correct |
287 ms |
21112 KB |
Output is correct |
16 |
Correct |
292 ms |
21128 KB |
Output is correct |
17 |
Correct |
273 ms |
21196 KB |
Output is correct |
18 |
Correct |
266 ms |
21056 KB |
Output is correct |
19 |
Correct |
278 ms |
21068 KB |
Output is correct |
20 |
Correct |
275 ms |
21328 KB |
Output is correct |
21 |
Correct |
280 ms |
21112 KB |
Output is correct |
22 |
Correct |
279 ms |
21144 KB |
Output is correct |
23 |
Correct |
114 ms |
15004 KB |
Output is correct |
24 |
Correct |
264 ms |
21020 KB |
Output is correct |
25 |
Correct |
8 ms |
4180 KB |
Output is correct |
26 |
Correct |
2 ms |
2772 KB |
Output is correct |
27 |
Correct |
2 ms |
2772 KB |
Output is correct |
28 |
Correct |
15 ms |
5588 KB |
Output is correct |
29 |
Correct |
8 ms |
4180 KB |
Output is correct |
30 |
Correct |
2 ms |
2900 KB |
Output is correct |
31 |
Correct |
3 ms |
2900 KB |
Output is correct |
32 |
Correct |
3 ms |
3028 KB |
Output is correct |
33 |
Correct |
2 ms |
2900 KB |
Output is correct |
34 |
Correct |
7 ms |
4180 KB |
Output is correct |
35 |
Correct |
2 ms |
2772 KB |
Output is correct |
36 |
Correct |
2 ms |
2772 KB |
Output is correct |
37 |
Correct |
2 ms |
2772 KB |
Output is correct |
38 |
Correct |
2 ms |
2772 KB |
Output is correct |
39 |
Correct |
2 ms |
2900 KB |
Output is correct |
40 |
Correct |
284 ms |
20828 KB |
Output is correct |
41 |
Correct |
264 ms |
21056 KB |
Output is correct |
42 |
Correct |
249 ms |
21244 KB |
Output is correct |
43 |
Correct |
96 ms |
14924 KB |
Output is correct |
44 |
Correct |
110 ms |
14976 KB |
Output is correct |
45 |
Correct |
227 ms |
20844 KB |
Output is correct |
46 |
Correct |
226 ms |
20696 KB |
Output is correct |
47 |
Correct |
244 ms |
21308 KB |
Output is correct |
48 |
Correct |
106 ms |
15044 KB |
Output is correct |
49 |
Correct |
203 ms |
20920 KB |
Output is correct |
50 |
Correct |
255 ms |
20900 KB |
Output is correct |
51 |
Correct |
242 ms |
24216 KB |
Output is correct |