Submission #210604

#	Time	Username	Problem	Language	Result	Execution time	Memory
210604		amiratou	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	495 ms	21428 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);
	int ans=dist[2][V],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;
}
//long long
//array bounds
//special cases
//binary search

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