Submission #960362

#	Time	Username	Problem	Language	Result	Execution time	Memory
960362		MrNanama	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	2051 ms	84172 KiB

commuter_pass

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back

using namespace std;
using ll = long long;

ll n,m,s,t,u,v;
ll ans;
vector<vector<pair<ll,ll>>> neigh;
unordered_map<ll, unordered_map<ll,ll>> dist;

vector<vector<ll>> parents;
vector<vector<ll>> kids;
vector<bool> important;

vector<ll> ds;
vector<ll> du;
vector<ll> dv;
vector<ll> dt;

vector<ll> dp_u;
vector<ll> dp_v;

void djkstra1(ll st, ll en){
	vector<bool> visited;
	vector<vector<int>> came_from;

	visited.assign(n,0);
	came_from.resize(n);
	important.assign(n,0);

	priority_queue<array<ll,3>, vector<array<ll,3>>, greater<array<ll,3>>> tasks;
	//tasks.push({0,st,st});

	ds[st] = 0;
	for(pair<ll,ll> go:neigh[st]){
		tasks.push({go.se, go.fi, st});
	}	


	while(!tasks.empty()){
		ll c = (tasks.top())[0];
		ll tar = (tasks.top())[1];
		ll fro = (tasks.top())[2];
		tasks.pop();


		if(ds[tar] == LLONG_MAX){
			ds[tar] = c;
			came_from[tar].pb(fro);
			parents[tar].pb(fro);
			kids[fro].pb(tar);
		}else if(c == ds[tar]){
			came_from[tar].pb(fro);
			parents[tar].pb(fro);
			kids[fro].pb(tar);
		}

		if(visited[tar]){continue;}

		for(pair<ll,ll> go:neigh[tar]){
			tasks.push({c+go.se, go.fi, tar});
		}

		visited[tar] = 1;
	}


	important[en] = 1;
	queue<ll> valuables;
	valuables.push(en);

	while(!valuables.empty()){
		ll curr = valuables.front();
		valuables.pop();

		for(ll a:parents[curr]){
			if(important[a] == 0){
				//this is unnecessary
				if(ds[a]+dist[a][curr] == ds[curr]){
					important[a] = 1; valuables.push(a);
				}
			}
		}
	}


	/*
	for(ll i=0; i<n; i++){
		cout << "imp " << i+1 << " " << important[i] << endl;
	}
	*/

	for(ll i=0; i<n; i++){
		if(important[i] == 0){
			parents[i].clear();
			kids[i].clear();
		}

		vector<ll> psd;
		for(int a:parents[i]){
			if(important[a]){psd.pb(a);}
		}

		parents[i] = psd;

		psd.clear();
		for(int a:kids[i]){
			if(important[a]){psd.pb(a);}
		}

		kids[i] = psd;
	}

	/*
	for(ll i=0; i<n; i++){
		cout << i+1 << ": ";
		for(ll go:kids[i]){
			cout << go+1 << " ";
		}
		cout << endl;
	}
	*/

}

void djkstra2(vector<ll> &vec, ll st){

	priority_queue<array<ll,3>, vector<array<ll,3>>, greater<array<ll,3>>> tasks;

	vector<ll> visited;
	visited.assign(n,0);

	vec[st] = 0;
	visited[st] = 1;

	for(pair<ll,ll> a:neigh[st]){
		tasks.push({a.se, a.fi, st});
	}

	while(!tasks.empty()){
		ll c = tasks.top()[0];
		ll tar = tasks.top()[1];
		ll fro = tasks.top()[2];

		tasks.pop();

		if(visited[tar]){continue;}
		visited[tar] = 1;
		vec[tar] = c;

		for(pair<ll,ll> go:neigh[tar]){
			tasks.push({c+go.se, go.fi});
		}
	}

}

inline void calc_dp_u(ll node){
	dp_u[node] = min<ll>(du[node],dp_u[node]);

	for(ll p:parents[node]){
		dp_u[node] = min<ll>(dp_u[p], dp_u[node]);
	}

	for(ll go:kids[node]){
		calc_dp_u(go);
	}
}

inline void calc_dp_v(ll node){
	dp_v[node] = min<ll>(dv[node],dp_v[node]);

	for(ll p:kids[node]){
		dp_v[node] = min<ll>(dp_v[p], dp_v[node]);
	}

	for(ll go:parents[node]){
		calc_dp_v(go);
	}
}

void dfs(ll node, ll &psd_ans){
	//maybe a protection against llong_max sum
	psd_ans = min<ll>(dp_u[node]+dp_v[node], psd_ans);

	for(ll go:kids[node]){dfs(go, psd_ans);}
}

ll solve(){
	ds.clear();
	ds.assign(n, LLONG_MAX);
	dt.clear();
	dt.assign(n, LLONG_MAX);
	du.clear();
	du.assign(n, LLONG_MAX);
	dv.clear();
	dv.assign(n, LLONG_MAX);

	dp_u.clear();
	dp_u.assign(n, LLONG_MAX);
	dp_v.clear();
	dp_v.assign(n, LLONG_MAX);

	parents.clear();
	parents.resize(n);
	kids.clear();
	kids.resize(n);
	important.clear();
	important.assign(n,0);

	djkstra1(s,t);
	djkstra2(du, u);
	djkstra2(dv, v);
	djkstra2(dt, t);

	calc_dp_u(s);
	calc_dp_v(t);

	ll psd_ans = LLONG_MAX;

	dfs(s, psd_ans);

	return psd_ans;

	return 0;
}


int main(){

	ios_base::sync_with_stdio(false); cin.tie(NULL);
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);

	cin >> n >> m >> s >> t >> u >> v;
	s--; t--; u--; v--;
	neigh.resize(n);
	parents.resize(n);
	kids.resize(n);

	ds.assign(n, LLONG_MAX);


	for(ll i=0; i<m; i++){
		ll n1,n2,c;
		cin >> n1 >> n2 >> c;
		n1--; n2--;

		neigh[n1].pb({n2,c});
		neigh[n2].pb({n1,c});

		dist[n1][n2] = c;
		dist[n2][n1] = c;
	}

	ans = solve();

	/*
	for(ll i=0; i<n; i++){
		cout << i+1 << ": ";
		for(int a:kids[i]){
			cout << a+1 << " ";
		}
		cout << endl;
	}
	*/

	ll psd;

	/*
	psd = s;
	s = t;
	t = psd;
	*/

	psd = u;
	u = v;
	v = psd;

	ans = min<ll>(ans, solve());
	ans = min<ll>(ans, du[v]);

	cout << ans << endl;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void djkstra2(std::vector<long long int>&, ll)':
commuter_pass.cpp:146:6: warning: unused variable 'fro' [-Wunused-variable]
  146 |   ll fro = tasks.top()[2];
      |      ^~~

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