#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
typedef long long ll;
#define fi first
#define se second
#define pll pair<ll,ll>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl;
#define MP make_pair
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define SZ(x) (ll)x.size()
#define ALL(x) x.begin(),x.end()
#define endl "\n"
const ll inf=1e18;
ll lowbit(ll x){return x&(-x);}
const ll maxn=1e5+5;
vector<pll>alist[maxn];
ll ds[maxn],dt[maxn],du[maxn],dv[maxn];
void dijkstra(ll st,ll dist[]){
rep(i,0,maxn)dist[i]=inf;
priority_queue<pll,vector<pll>,greater<pll>>s;
s.push(MP(0ll,st));
dist[st]=0;
while(!s.empty()){
auto u=s.top();
s.pop();
if(u.fi!=dist[u.se])continue;
for(auto x:alist[u.se]){
if(x.fi+u.fi<dist[x.se]){
dist[x.se]=x.fi+u.fi;
s.push(MP(dist[x.se],x.se));
}
}
}
}
ll f[maxn],ff[maxn];
ll n,m;
ll t;
void dijk(ll orig[],ll dist[]){
priority_queue<pll,vector<pll>,greater<pll>>s;
rep(i,1,n+1){
dist[i]=orig[i];
s.push(MP(orig[i],i));
}
while(!s.empty()){
auto u=s.top();
s.pop();
if(u.fi!=dist[u.se])continue;
for(auto x:alist[u.se]){
//the edge is on the path from s to t => free
if(ds[x.se]+x.fi+dt[u.se]==ds[t] and dist[u.se]<dist[x.se]){
dist[x.se]=dist[u.se];
s.push(MP(dist[x.se],x.se));
}
}
}
}
ll s;
ll u,v;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
cin>>s>>t;
cin>>u>>v;
rep(i,0,m){
ll a,b,c;cin>>a>>b>>c;
alist[a].pb(MP(c,b));
alist[b].pb(MP(c,a));
}
dijkstra(s,ds);
dijkstra(t,dt);
dijkstra(u,du);
dijkstra(v,dv);
dijk(dv,f);
dijk(du,ff);
ll ans=inf;
rep(i,1,n+1){
ans=min(ans,du[i]+f[i]);
ans=min(ans,dv[i]+ff[i]);
}
cout<<ans<<endl;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
244 ms |
21672 KB |
Output is correct |
2 |
Correct |
227 ms |
21460 KB |
Output is correct |
3 |
Correct |
257 ms |
21256 KB |
Output is correct |
4 |
Correct |
223 ms |
21376 KB |
Output is correct |
5 |
Correct |
273 ms |
21328 KB |
Output is correct |
6 |
Correct |
234 ms |
21420 KB |
Output is correct |
7 |
Correct |
297 ms |
21408 KB |
Output is correct |
8 |
Correct |
233 ms |
21464 KB |
Output is correct |
9 |
Correct |
221 ms |
22036 KB |
Output is correct |
10 |
Correct |
212 ms |
21408 KB |
Output is correct |
11 |
Correct |
88 ms |
16296 KB |
Output is correct |
12 |
Correct |
266 ms |
21380 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
242 ms |
21448 KB |
Output is correct |
2 |
Correct |
276 ms |
21772 KB |
Output is correct |
3 |
Correct |
264 ms |
21288 KB |
Output is correct |
4 |
Correct |
245 ms |
21536 KB |
Output is correct |
5 |
Correct |
238 ms |
21536 KB |
Output is correct |
6 |
Correct |
225 ms |
21228 KB |
Output is correct |
7 |
Correct |
272 ms |
21664 KB |
Output is correct |
8 |
Correct |
238 ms |
21464 KB |
Output is correct |
9 |
Correct |
272 ms |
21396 KB |
Output is correct |
10 |
Correct |
265 ms |
21456 KB |
Output is correct |
11 |
Correct |
86 ms |
16296 KB |
Output is correct |
12 |
Correct |
231 ms |
21488 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
8536 KB |
Output is correct |
2 |
Correct |
2 ms |
7256 KB |
Output is correct |
3 |
Correct |
2 ms |
7260 KB |
Output is correct |
4 |
Correct |
11 ms |
10660 KB |
Output is correct |
5 |
Correct |
6 ms |
9052 KB |
Output is correct |
6 |
Correct |
2 ms |
7260 KB |
Output is correct |
7 |
Correct |
2 ms |
7512 KB |
Output is correct |
8 |
Correct |
3 ms |
7516 KB |
Output is correct |
9 |
Correct |
2 ms |
7260 KB |
Output is correct |
10 |
Correct |
7 ms |
9052 KB |
Output is correct |
11 |
Correct |
2 ms |
7260 KB |
Output is correct |
12 |
Correct |
2 ms |
7260 KB |
Output is correct |
13 |
Correct |
2 ms |
7260 KB |
Output is correct |
14 |
Correct |
2 ms |
7332 KB |
Output is correct |
15 |
Correct |
2 ms |
7260 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
244 ms |
21672 KB |
Output is correct |
2 |
Correct |
227 ms |
21460 KB |
Output is correct |
3 |
Correct |
257 ms |
21256 KB |
Output is correct |
4 |
Correct |
223 ms |
21376 KB |
Output is correct |
5 |
Correct |
273 ms |
21328 KB |
Output is correct |
6 |
Correct |
234 ms |
21420 KB |
Output is correct |
7 |
Correct |
297 ms |
21408 KB |
Output is correct |
8 |
Correct |
233 ms |
21464 KB |
Output is correct |
9 |
Correct |
221 ms |
22036 KB |
Output is correct |
10 |
Correct |
212 ms |
21408 KB |
Output is correct |
11 |
Correct |
88 ms |
16296 KB |
Output is correct |
12 |
Correct |
266 ms |
21380 KB |
Output is correct |
13 |
Correct |
242 ms |
21448 KB |
Output is correct |
14 |
Correct |
276 ms |
21772 KB |
Output is correct |
15 |
Correct |
264 ms |
21288 KB |
Output is correct |
16 |
Correct |
245 ms |
21536 KB |
Output is correct |
17 |
Correct |
238 ms |
21536 KB |
Output is correct |
18 |
Correct |
225 ms |
21228 KB |
Output is correct |
19 |
Correct |
272 ms |
21664 KB |
Output is correct |
20 |
Correct |
238 ms |
21464 KB |
Output is correct |
21 |
Correct |
272 ms |
21396 KB |
Output is correct |
22 |
Correct |
265 ms |
21456 KB |
Output is correct |
23 |
Correct |
86 ms |
16296 KB |
Output is correct |
24 |
Correct |
231 ms |
21488 KB |
Output is correct |
25 |
Correct |
7 ms |
8536 KB |
Output is correct |
26 |
Correct |
2 ms |
7256 KB |
Output is correct |
27 |
Correct |
2 ms |
7260 KB |
Output is correct |
28 |
Correct |
11 ms |
10660 KB |
Output is correct |
29 |
Correct |
6 ms |
9052 KB |
Output is correct |
30 |
Correct |
2 ms |
7260 KB |
Output is correct |
31 |
Correct |
2 ms |
7512 KB |
Output is correct |
32 |
Correct |
3 ms |
7516 KB |
Output is correct |
33 |
Correct |
2 ms |
7260 KB |
Output is correct |
34 |
Correct |
7 ms |
9052 KB |
Output is correct |
35 |
Correct |
2 ms |
7260 KB |
Output is correct |
36 |
Correct |
2 ms |
7260 KB |
Output is correct |
37 |
Correct |
2 ms |
7260 KB |
Output is correct |
38 |
Correct |
2 ms |
7332 KB |
Output is correct |
39 |
Correct |
2 ms |
7260 KB |
Output is correct |
40 |
Correct |
214 ms |
24768 KB |
Output is correct |
41 |
Correct |
212 ms |
25488 KB |
Output is correct |
42 |
Correct |
221 ms |
25680 KB |
Output is correct |
43 |
Correct |
90 ms |
18336 KB |
Output is correct |
44 |
Correct |
97 ms |
18456 KB |
Output is correct |
45 |
Correct |
210 ms |
24728 KB |
Output is correct |
46 |
Correct |
231 ms |
25028 KB |
Output is correct |
47 |
Correct |
227 ms |
25672 KB |
Output is correct |
48 |
Correct |
106 ms |
17832 KB |
Output is correct |
49 |
Correct |
204 ms |
24212 KB |
Output is correct |
50 |
Correct |
212 ms |
25408 KB |
Output is correct |
51 |
Correct |
196 ms |
24684 KB |
Output is correct |