This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// FUCKED UP FUCKED UP FUCKED UP FUCKED UP FUCKED UP
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O2,no-stack-protector,unroll-loops,fast-math")
#define F first
#define S second
#define pb push_back
#define SZ(x) (ll)(x.size())
#define all(x) x.begin(),x.end()
#define MP make_pair
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll maxn=2e5+10, maxm=1e6+10, lg=15, mod=1e9+7, inf=1e18;
ll n,m,S,T,A,B,V[maxn],U[maxn],W[maxn],d1[maxn],d2[maxn],d3[maxn],ans;
vector<ll> g[maxn],in[maxn];
void dij(ll src,ll dis[]){
for(int i=1;i<=n;i++) in[i].clear(), dis[i]=inf;
priority_queue<pll,vector<pll>,greater<pll>> q;
q.push({dis[src]=0,src});
while(!q.empty()){
ll v=q.top().S; q.pop();
for(auto i:g[v]){
ll u=v^V[i]^U[i],w=W[i];
if(dis[u]>dis[v]+w){
in[u].clear();
q.push({dis[u]=dis[v]+w,u});
}
if(dis[u]==dis[v]+w) in[u].pb(v);
}
}
}
pll dfs(ll v){
ll m1=d1[v],m2=d2[v];
for(auto u:in[v]){
pll p=dfs(u);
m1=min(m1,p.F);
m2=min(m2,p.S);
}
ans=min({ans,m1+d2[v],d1[v]+m2});
return {m1,m2};
}
int main(){
ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m>>S>>T>>A>>B;
for(int i=0;i<m;i++){
cin>>V[i]>>U[i]>>W[i];
g[V[i]].pb(i), g[U[i]].pb(i);
}
dij(A,d1), dij(B,d2);
dij(S,d3);
return 0;
ans=d1[B];
dfs(T);
cout<<ans;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |