Submission #260238

#	Time	Username	Problem	Language	Result	Execution time	Memory
260238		Goolakh	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	706 ms	37012 KiB

commuter_pass

// 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 mm[maxn];
bool mk[maxn];
pll dfs(ll v){
	if(mk[v]) return mm[v];
	mk[v]=1;
	mm[v]={d1[v],d2[v]};
	for(auto u:in[v]){
		pll p=dfs(u);
		mm[v].F=min(mm[v].F,p.F);
		mm[v].S=min(mm[v].S,p.S);
	}
	ans=min({ans,mm[v].F+d2[v],d1[v]+mm[v].S});
	return mm[v];
}

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);
	ans=d1[B];
	dfs(T);
	cout<<ans;
	
	return 0;
}



 

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45