Submission #501090

#	Time	Username	Problem	Language	Result	Execution time	Memory
501090		codr0	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	990 ms	32396 KiB

commuter_pass

// Code by Parsa Eslami

#include <bits/stdc++.h>
#define int long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define S second
#define F first
#define pb push_back
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define err(x) cout<<#x<<": "<<x<<'\n';

using namespace std;
typedef pair<int,int> pii;
const int N=1e5+4;
const int INF=1e15;
int valV[N],valU[N];
pii distS[N];
pii distT[N];
vector<int> adj[N];
vector<int> w[N];
int n,m;
int s,t,u,v;
	
	void FILLvalV(){
		FOR(i,1,n) valV[i]=INF;
		valV[v]=0;
		set<pii> st;
		FOR(i,1,n) st.insert({valV[i],i});
		while(!st.empty()){
			pii mn=*(st.begin());
			st.erase(mn);
			int o=mn.S;
			FOR(i,0,SZ(adj[o])-1){
				int p=adj[o][i];
				int wp=w[o][i];
				if((valV[o]+wp)<valV[p]){
					st.erase({valV[p],p});
					valV[p]=valV[o]+wp;
					st.insert({valV[p],p});
				}
			}
		}
	}

	void FILLvalU(){
		FOR(i,1,n) valU[i]=INF;
		valU[u]=0;
		set<pii> st;
		FOR(i,1,n) st.insert({valU[i],i});
		while(!st.empty()){
			pii mn=*(st.begin());
			st.erase(mn);
			int o=mn.S;
			FOR(i,0,SZ(adj[o])-1){
				int p=adj[o][i];
				int wp=w[o][i];
				if((valU[o]+wp)<valU[p]){
					st.erase({valU[p],p});
					valU[p]=valU[o]+wp;
					st.insert({valU[p],p});
				}
			}
		}
	}

	void FILLdistS(){
		FOR(i,1,n) distS[i]={INF,INF};
		distS[s]={0,valV[s]};
		set<pair<pii,int>> st;
		FOR(i,1,n) st.insert({distS[i],i});
		while(!st.empty()){
			pair<pii,int> x0=*(st.begin());
			st.erase(x0);
			int o=x0.S;
			FOR(i,0,SZ(adj[o])-1){
				int p=adj[o][i];
				int wp=w[o][i];
				pii nwp={wp+distS[o].F,min(distS[o].S,valV[p])};
				if(nwp<distS[p]){
					st.erase({distS[p],p});
					distS[p]=nwp;
					st.insert({distS[p],p});
				}
			}
		}
	}

	void FILLdistT(){
		FOR(i,1,n) distT[i]={INF,INF};
		distT[t]={0,valV[t]};
		set<pair<pii,int>> st;
		FOR(i,1,n) st.insert({distT[i],i});
		while(!st.empty()){
			pair<pii,int> x0=*(st.begin());
			st.erase(x0);
			int o=x0.S;
			FOR(i,0,SZ(adj[o])-1){
				int p=adj[o][i];
				int wp=w[o][i];
				pii nwp={wp+distT[o].F,min(distT[o].S,valV[p])};
				if(nwp<distT[p]){
					st.erase({distT[p],p});
					distT[p]=nwp;
					st.insert({distT[p],p});
				}
			}
		}
	}

	int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin>>n>>m>>s>>t>>u>>v;
	FOR(i,1,m){
		int U,V,W; cin>>U>>V>>W;
		adj[U].pb(V);
		w[U].pb(W);
		adj[V].pb(U);
		w[V].pb(W);
	}
	FILLvalV();
	FILLvalU();
	FILLdistS();
	FILLdistT();
	int ans=valV[u];
	int r=distS[t].F;
	FOR(i,1,n){
		if((distS[i].F+distT[i].F)==r){
			ans=min(ans,valU[i]+min(distS[i].S,distT[i].S));
		}
	}
	cout<<ans<<'\n';
	
	return 0;
    }

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