Submission #210603

#	Time	Username	Problem	Language	Result	Execution time	Memory
210603		amiratou	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	481 ms	24356 KiB

commuter_pass

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define rando mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define fi first
#define se second
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define debugii(x) cerr << " - " << #x << ": " << x.fi<<","<<x.se << endl;
#define sep() cerr << "--------------------" << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ld long double
#define ll long long
#define int ll
#define ii pair<int,int>
#define v vector<int>
#define vii vector<ii>
#define vv vector<vector<ii> >
#define mp make_pair
#define INF 1e15
#define pb push_back
#define EPS 1e-9
const int MOD = 1000000007; // 998244353
int dist[6][100005];//1,n,U,V
int D[301][301];
int n,m,a,b,c;
vv vec;
void sssp(int node,int idx){
	for (int i = 0; i < n; ++i)
		dist[idx][i]=INF;
	dist[idx][node]=0;
	priority_queue<ii,vii,greater<ii> > pq;
	pq.push(ii(0,node));
	while(!pq.empty()){
		ii f=pq.top();
		pq.pop();
		if(dist[idx][f.se]<f.fi)
			continue;
		for(auto it:vec[f.se])
			if(dist[idx][it.fi]>(f.fi+it.se))
				dist[idx][it.fi]=f.fi+it.se,pq.push(ii(dist[idx][it.fi],it.fi));
	}
}
int32_t main(){
	boost;
	//freopen(".in","r",stdin);
	cin>>n>>m;
	int S,T,U,V;
	cin>>S>>T>>U>>V;
	S--,T--,U--,V--;
	vec.resize(n);
	while(m--){
		cin>>a>>b>>c;
		a--,b--;
		vec[a].pb(ii(b,c));
		vec[b].pb(ii(a,c));
	}
	sssp(S,0),sssp(T,1),sssp(U,2),sssp(V,3);
	if(S==U){
		int ans=INF;
		for (int i = 0; i < n; ++i)
			if((dist[0][i]+dist[1][i])==dist[0][T])
				ans=min(ans,dist[3][i]);
		cout<<ans;
	}
	else{
		int ans=dist[2][V];
		if(n<=300){
			for (int i = 0; i < n; ++i){
				for (int j = 0; j < n; ++j)
					if(i!=j)D[i][j]=INF;
				for(auto it:vec[i])
					D[i][it.fi]=it.se;
			}
			for (int k = 0; k < n; ++k)
				for (int i = 0; i < n; ++i)
					for (int j = 0; j < n; ++j)
						if(D[i][k]!=INF&&D[k][j]!=INF)
							D[i][j]=min(D[i][j],D[i][k]+D[k][j]);
			for (int i = 0; i < n; ++i)
			{
				if((dist[0][i]+dist[1][i])!=dist[0][T])continue;
				for (int j = 0; j < n; ++j)
				{
					if((dist[0][j]+dist[1][j])!=dist[0][T])continue;
					if((dist[0][i]+dist[1][j]+D[i][j])==dist[0][T])
						ans=min(ans,min(dist[2][i]+dist[3][j],dist[3][i]+dist[2][j]));
				}
			}
			cout<<ans;
			return 0;
		}
		else{
			int mini=INF,m2=INF;
			for (int i = 0; i < n; ++i)
			{
				if((dist[0][i]+dist[1][i])!=dist[0][T])continue;
				if(dist[2][i]<mini)
					mini=dist[2][i],a=i;
				if(dist[3][i]<m2)
					m2=dist[3][i],b=i;
			}
			sssp(a,4),sssp(b,5);
			if((dist[0][a]+dist[1][b]+dist[4][b])==dist[0][T]||(dist[0][b]+dist[1][a]+dist[4][b])==dist[0][T])
				ans=min(ans,mini+m2);
			else{
				int dd=INF;
				for (int i = 0; i < n; ++i)
					if((dist[0][i]+dist[1][a]+dist[4][i])==dist[0][T]||(dist[1][i]+dist[0][a]+dist[4][i])==dist[0][T])
						dd=min(dd,dist[3][i]);
				ans=min(ans,dd+mini);
				dd=INF;
				for (int i = 0; i < n; ++i)
					if((dist[0][i]+dist[1][b]+dist[5][i])==dist[0][T]||(dist[1][i]+dist[0][b]+dist[5][i])==dist[0][T])
						dd=min(dd,dist[2][i]);
				ans=min(ans,dd+m2);
			}
			cout<<ans;
			return 0;
		}
		a=INF,b=INF;
		for (int i = 0; i < n; ++i)
			if((dist[0][i]+dist[1][i])==dist[0][T])
				a=min(a,dist[2][i]),b=min(b,dist[3][i]);
		ans=min(ans,a+b);
		cout<<ans;
	}
	return 0;
}
//long long
//array bounds
//special cases
//binary search

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