#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define rando mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define fi first
#define se second
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define debugii(x) cerr << " - " << #x << ": " << x.fi<<","<<x.se << endl;
#define sep() cerr << "--------------------" << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ld long double
#define ll long long
#define int ll
#define ii pair<int,int>
#define v vector<int>
#define vii vector<ii>
#define vv vector<vector<ii> >
#define mp make_pair
#define INF 1e15
#define pb push_back
#define EPS 1e-9
const int MOD = 1000000007; // 998244353
int dist[6][100005];//1,n,U,V
int D[301][301];
int n,m,a,b,c;
vv vec;
void sssp(int node,int idx){
for (int i = 0; i < n; ++i)
dist[idx][i]=INF;
dist[idx][node]=0;
priority_queue<ii,vii,greater<ii> > pq;
pq.push(ii(0,node));
while(!pq.empty()){
ii f=pq.top();
pq.pop();
if(dist[idx][f.se]<f.fi)
continue;
for(auto it:vec[f.se])
if(dist[idx][it.fi]>(f.fi+it.se))
dist[idx][it.fi]=f.fi+it.se,pq.push(ii(dist[idx][it.fi],it.fi));
}
}
int32_t main(){
boost;
//freopen(".in","r",stdin);
cin>>n>>m;
int S,T,U,V;
cin>>S>>T>>U>>V;
S--,T--,U--,V--;
vec.resize(n);
while(m--){
cin>>a>>b>>c;
a--,b--;
vec[a].pb(ii(b,c));
vec[b].pb(ii(a,c));
}
sssp(S,0),sssp(T,1),sssp(U,2),sssp(V,3);
if(S==U){
int ans=INF;
for (int i = 0; i < n; ++i)
if((dist[0][i]+dist[1][i])==dist[0][T])
ans=min(ans,dist[3][i]);
cout<<ans;
}
else{
int ans=dist[2][V];
if(n<=300){
for (int i = 0; i < n; ++i){
for (int j = 0; j < n; ++j)
if(i!=j)D[i][j]=INF;
for(auto it:vec[i])
D[i][it.fi]=it.se;
}
for (int k = 0; k < n; ++k)
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if(D[i][k]!=INF&&D[k][j]!=INF)
D[i][j]=min(D[i][j],D[i][k]+D[k][j]);
for (int i = 0; i < n; ++i)
{
if((dist[0][i]+dist[1][i])!=dist[0][T])continue;
for (int j = 0; j < n; ++j)
{
if((dist[0][j]+dist[1][j])!=dist[0][T])continue;
if((dist[0][i]+dist[1][j]+D[i][j])==dist[0][T])
ans=min(ans,min(dist[2][i]+dist[3][j],dist[3][i]+dist[2][j]));
}
}
cout<<ans;
return 0;
}
else{
int mini=INF,m2=INF;
for (int i = 0; i < n; ++i)
{
if((dist[0][i]+dist[1][i])!=dist[0][T])continue;
if(dist[2][i]<mini)
mini=dist[2][i],a=i;
if(dist[3][i]<m2)
m2=dist[3][i],b=i;
}
sssp(a,4),sssp(b,5);
if((dist[0][a]+dist[1][b]+dist[4][b])==dist[0][T]||(dist[0][b]+dist[1][a]+dist[4][b])==dist[0][T])
ans=min(ans,mini+m2);
else{
int dd=INF;
for (int i = 0; i < n; ++i)
if((dist[0][i]+dist[1][a]+dist[4][i])==dist[0][T]||(dist[1][i]+dist[0][a]+dist[4][i])==dist[0][T])
dd=min(dd,dist[3][i]);
ans=min(ans,dd+mini);
dd=INF;
for (int i = 0; i < n; ++i)
if((dist[0][i]+dist[1][b]+dist[5][i])==dist[0][T]||(dist[1][i]+dist[0][b]+dist[5][i])==dist[0][T])
dd=min(dd,dist[2][i]);
ans=min(ans,dd+m2);
}
cout<<ans;
return 0;
}
a=INF,b=INF;
for (int i = 0; i < n; ++i)
if((dist[0][i]+dist[1][i])==dist[0][T])
a=min(a,dist[2][i]),b=min(b,dist[3][i]);
ans=min(ans,a+b);
cout<<ans;
}
return 0;
}
//long long
//array bounds
//special cases
//binary search
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
338 ms |
19528 KB |
Output is correct |
2 |
Correct |
340 ms |
18336 KB |
Output is correct |
3 |
Correct |
343 ms |
18028 KB |
Output is correct |
4 |
Correct |
344 ms |
19328 KB |
Output is correct |
5 |
Correct |
351 ms |
18212 KB |
Output is correct |
6 |
Correct |
351 ms |
19516 KB |
Output is correct |
7 |
Correct |
330 ms |
18084 KB |
Output is correct |
8 |
Correct |
338 ms |
18172 KB |
Output is correct |
9 |
Correct |
339 ms |
18160 KB |
Output is correct |
10 |
Correct |
289 ms |
18000 KB |
Output is correct |
11 |
Correct |
128 ms |
11256 KB |
Output is correct |
12 |
Correct |
372 ms |
18184 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
481 ms |
19904 KB |
Output is correct |
2 |
Correct |
469 ms |
19856 KB |
Output is correct |
3 |
Correct |
459 ms |
19872 KB |
Output is correct |
4 |
Correct |
474 ms |
19884 KB |
Output is correct |
5 |
Correct |
464 ms |
19740 KB |
Output is correct |
6 |
Correct |
429 ms |
19524 KB |
Output is correct |
7 |
Correct |
468 ms |
19728 KB |
Output is correct |
8 |
Correct |
469 ms |
19856 KB |
Output is correct |
9 |
Correct |
465 ms |
19844 KB |
Output is correct |
10 |
Correct |
479 ms |
19792 KB |
Output is correct |
11 |
Correct |
161 ms |
12792 KB |
Output is correct |
12 |
Correct |
441 ms |
19532 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
71 ms |
2552 KB |
Output is correct |
2 |
Correct |
52 ms |
1144 KB |
Output is correct |
3 |
Correct |
52 ms |
1144 KB |
Output is correct |
4 |
Correct |
85 ms |
3832 KB |
Output is correct |
5 |
Correct |
72 ms |
2552 KB |
Output is correct |
6 |
Correct |
59 ms |
1144 KB |
Output is correct |
7 |
Correct |
63 ms |
1272 KB |
Output is correct |
8 |
Correct |
64 ms |
1272 KB |
Output is correct |
9 |
Correct |
64 ms |
1272 KB |
Output is correct |
10 |
Correct |
71 ms |
2552 KB |
Output is correct |
11 |
Correct |
30 ms |
1148 KB |
Output is correct |
12 |
Correct |
36 ms |
1144 KB |
Output is correct |
13 |
Correct |
52 ms |
1144 KB |
Output is correct |
14 |
Correct |
58 ms |
1144 KB |
Output is correct |
15 |
Correct |
58 ms |
1144 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
338 ms |
19528 KB |
Output is correct |
2 |
Correct |
340 ms |
18336 KB |
Output is correct |
3 |
Correct |
343 ms |
18028 KB |
Output is correct |
4 |
Correct |
344 ms |
19328 KB |
Output is correct |
5 |
Correct |
351 ms |
18212 KB |
Output is correct |
6 |
Correct |
351 ms |
19516 KB |
Output is correct |
7 |
Correct |
330 ms |
18084 KB |
Output is correct |
8 |
Correct |
338 ms |
18172 KB |
Output is correct |
9 |
Correct |
339 ms |
18160 KB |
Output is correct |
10 |
Correct |
289 ms |
18000 KB |
Output is correct |
11 |
Correct |
128 ms |
11256 KB |
Output is correct |
12 |
Correct |
372 ms |
18184 KB |
Output is correct |
13 |
Correct |
481 ms |
19904 KB |
Output is correct |
14 |
Correct |
469 ms |
19856 KB |
Output is correct |
15 |
Correct |
459 ms |
19872 KB |
Output is correct |
16 |
Correct |
474 ms |
19884 KB |
Output is correct |
17 |
Correct |
464 ms |
19740 KB |
Output is correct |
18 |
Correct |
429 ms |
19524 KB |
Output is correct |
19 |
Correct |
468 ms |
19728 KB |
Output is correct |
20 |
Correct |
469 ms |
19856 KB |
Output is correct |
21 |
Correct |
465 ms |
19844 KB |
Output is correct |
22 |
Correct |
479 ms |
19792 KB |
Output is correct |
23 |
Correct |
161 ms |
12792 KB |
Output is correct |
24 |
Correct |
441 ms |
19532 KB |
Output is correct |
25 |
Correct |
71 ms |
2552 KB |
Output is correct |
26 |
Correct |
52 ms |
1144 KB |
Output is correct |
27 |
Correct |
52 ms |
1144 KB |
Output is correct |
28 |
Correct |
85 ms |
3832 KB |
Output is correct |
29 |
Correct |
72 ms |
2552 KB |
Output is correct |
30 |
Correct |
59 ms |
1144 KB |
Output is correct |
31 |
Correct |
63 ms |
1272 KB |
Output is correct |
32 |
Correct |
64 ms |
1272 KB |
Output is correct |
33 |
Correct |
64 ms |
1272 KB |
Output is correct |
34 |
Correct |
71 ms |
2552 KB |
Output is correct |
35 |
Correct |
30 ms |
1148 KB |
Output is correct |
36 |
Correct |
36 ms |
1144 KB |
Output is correct |
37 |
Correct |
52 ms |
1144 KB |
Output is correct |
38 |
Correct |
58 ms |
1144 KB |
Output is correct |
39 |
Correct |
58 ms |
1144 KB |
Output is correct |
40 |
Correct |
410 ms |
20572 KB |
Output is correct |
41 |
Correct |
462 ms |
19764 KB |
Output is correct |
42 |
Correct |
431 ms |
19788 KB |
Output is correct |
43 |
Correct |
166 ms |
12792 KB |
Output is correct |
44 |
Correct |
171 ms |
14712 KB |
Output is correct |
45 |
Correct |
393 ms |
22152 KB |
Output is correct |
46 |
Correct |
392 ms |
22420 KB |
Output is correct |
47 |
Correct |
436 ms |
23548 KB |
Output is correct |
48 |
Correct |
175 ms |
14200 KB |
Output is correct |
49 |
Correct |
366 ms |
24356 KB |
Output is correct |
50 |
Correct |
409 ms |
22944 KB |
Output is correct |
51 |
Correct |
375 ms |
22688 KB |
Output is correct |