Submission #714149

#	Time	Username	Problem	Language	Result	Execution time	Memory
714149		william950615	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	747 ms	86736 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define mkp make_pair
#define MEM(x) memset(x, 0, sizeof(x))
#define SZ(x) int(x.size())
#define ALL(x) begin(x), end(x)
#define REP(i,n) for( int i = 0; i < n; ++i )
#define FOR(i,a,b) for( int i = (a); i <= b; ++i )
#define RFOR(i,a,b) for( int i = (a); i >= b; --i )
#define EB emplace_back
#define EP emplace


#ifdef DEBUG
	template<typename T> void _DO(T&&x){cerr << x << '\n';}
	template<typename A, typename ...B> void _DO(A&&a, B&&...b){cerr << a <<','; _DO(b...);};
	#define de(...) do{\
		fprintf(stderr, "%s-%d (%s):", __func__, __LINE__, #__VA_ARGS__);\
		_DO(__VA_ARGS__);\
	}while(0);
#else
	#define de(...)
#endif
typedef long long ll;
typedef pair<int,int> pii;
typedef array<ll, 3> arr;
template<typename T> 
using V = vector<T>;

constexpr int mxN = 3e5+2;
constexpr ll inf = 1e18;

vector<arr> graph[ mxN ];
bitset<mxN> tvis;

struct ShortPath {
	int st;
	V<ll> dis;
	V<V<int>> tree;

	V<bool>  vis;


	void DO() {
		priority_queue< arr, V<arr>, greater<arr>> pq;
		pq .EP( arr{0, st, st} );
		while( !pq.empty() ) {
			auto a = pq.top(); pq.pop();
			if( dis[ a[1] ] != inf ) {
				if( dis[ a[1] ] == a[0] && a[2] != a[1] ) {
					tree[ a[2] ].push_back( a[1] );
				}
				continue;
			}
			dis[ a[1] ] = a[0];
			if( a[2] != a[1] )
				tree[ a[2] ].push_back( a[1] );


			for( auto &i : graph[ a[1] ] ) {
				if( dis[ i[1] ] != inf ) continue;
				pq.EP( arr{ a[0]+i[0], i[1], a[1] });
			}
		}
	};

	void getMinU( int cur, const int u, const ShortPath& fromu,V<ll>& minval, V<int>& cantgo ) {
		ll mn = inf;
		tvis[ cur ] = true;
		for( auto &i : tree[ cur ] ) {
			if( !tvis[ i ] )
				getMinU( i, u, fromu, minval, cantgo );	
			cantgo[ cur ] = ( cantgo[ cur ] &cantgo[ i ] );
			mn = min( minval[ i ], mn );
		}
		if( !cantgo[ cur ] ) minval[ cur ] = min( mn, fromu( cur ) ); 
	}
	
	ll operator() (int t ) const {
		return dis[ t ] ;
	};
	
	ShortPath( int _st ) {
		st = _st;
		dis.assign(mxN, inf);
		tree.assign(mxN, V<int>());
		vis.assign( mxN, false );
		DO();
	};
};


inline void solve() {
	int N, M; cin >> N >> M;
	int s, t; cin >> s >> t;
	int u, v; cin >> u >> v;
	REP(edge, M ){
		int a, b, c;
		cin >> a >> b >> c;
		graph[ a ].EB( arr{c,b,edge+1} );
		graph[ b ].EB( arr{c,a,edge+1} );
	}


	// make shortest path
	ShortPath froms(s), fromu(u), fromv(v), fromt(t);

	V<int> vcantgo(mxN, true), ucantgo( mxN, true);
	vcantgo[ t ] = ucantgo[ t ] = false;

	V<ll> vminval(mxN, inf), uminval( mxN, inf );
	froms.getMinU( s, u, fromu, uminval, ucantgo ) ;
	tvis.reset();
	froms.getMinU( s, v, fromv, vminval, vcantgo ) ;



	ll ans = fromu(v);
	ll minv = inf, minu = inf;
	for( int i =1; i <= N; ++i ) {
		if( froms(i) + fromt(i) == froms(t)  ) {
			if( !ucantgo[ i ] )
				ans = min( ans, fromv(i) + uminval[ i ] );
			if( !vcantgo[ i ] )
				ans = min( ans, fromu(i) + vminval[ i ] );
		}
	}


	// check if (u, v) is on the shortest path

	/*
	for( int i = 1; i <= N; ++i ) {
		cout << froms(i) << ' ';
	}
	cout << '\n';
	for( int i = 1; i <= N; ++i ) {
		cout << fromt(i) << ' ';
	}
	cout << '\n';
	*/
	de( ans, minv, minu );
	cout << min( ans, minv + minu ) << '\n';
}

int main () {
	int T = 1;	
#ifdef Local
	cin >> T;
#endif
	while(T--) solve();
}

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