Submission #638429

#	Time	Username	Problem	Language	Result	Execution time	Memory
638429		KYoA_A	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	430 ms	35116 KiB

commuter_pass

/*---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---*/

#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define dbg(x...)
#endif

#define rep(i, a, b)	for(int i = a; i < (b); ++i)
#define rrep(a, b, c)	for(int a = (b); a > c; --a)
#define each(a, b)	for(auto& a : b)

#define sz(x)       (int)(x).size()
#define all(a)      (a).begin(),(a).end()
#define rall(a)     (a).rbegin(), (a).rend()

#define vi vector<int>
#define ar array

template<class T> using V = vector<T>;
template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;

#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define rsz resize
#define bk back()

#define pi pair<int, int>
#define pl pair<ll, ll>
#define mp make_pair
#define f first
#define s second

#define pct(x) __builtin_popcount(x)
constexpr int fsb(int x) {return __builtin_ffs(x) - 1;} // first set bit
constexpr int log2(int x) {return x == 0 ? 0 : 31-__builtin_clz(x);} // floor(log2(x))
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

template <class T> bool umin(T& a, const T& b){return b<a?a=b, 1:0;}
template <class T> bool umax(T& a, const T& b){return a<b?a=b, 1:0;}

const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};

using ll = long long;
using ld = long double;
using str = string;

const int inf = (int)1e9 + 5;
const ll infl = (ll)1e18 + 5;
const ld PI = acos((ld)-1);
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;

/*---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---*/

#define int ll
int n, m, s, t, u, v;
V<V<pi>> g(N);
V<vi> ad(N);

void solve(){
	cin >> n >> m >> s >> t >> u >> v;

	--s; --t; --u; --v;

	rep(i, 0, m){
		int a, b, c; cin >> a >> b >> c;
		g[--a].eb(--b, c);
		g[b].eb(a, c);
	}
	
	// DIJkstra
	pqg <pl> pq;
	V<ll> d(n, infl);
	V<vi> p(n);
	pq.emplace(d[s] = 0, s);
	V<bool> vis(n);

	while(!pq.empty()){
		auto [od, x] = pq.top(); pq.pop();
		if(d[x] != od) continue;
		for(auto [y, e] : g[x]){
			if(umin(d[y], od + e)){
				p[y].clear();
				pq.emplace(d[y], y);
			}
			if(d[y] == od + e){
				p[y].eb(x);
			}
		}
	}

	function<void(int)> dfs = [&](int s){
		vis[s] = 1;
		each(x, p[s]) if(!vis[x]){
			dfs(x);
		}
	};

	dfs(t);

	rep(i, 0, n){
		if(!vis[i]){
			p[i].clear(); continue;
		}

		rep(j, 0, sz(p[i])){
			auto &x = p[i][j];
			if(!vis[x]){
				swap(x, p[i].bk);
				p[i].pop_back(); --j;
			}
		}
	}

	rep(i, 0, n) if(vis[i]){
		each(x, p[i]){
			ad[x].eb(i);
		}
	}

	d = V<ll> (4*n, infl);
	pq.emplace(d[u] = 0, u);

	while(!pq.empty()){
		auto [od, x] = pq.top(); pq.pop();
		if(d[x] != od) continue;

		int zx = x;
		while(x >= n) x -= n;

		if(zx < 2*n){
			for(auto y : ad[x]){
				if(umin(d[y += n], od)){
					pq.emplace(d[y], y);
				}
			}
		}

		if((zx < n || zx >= 2*n) && zx < 3*n){
			for(auto y : p[x]){
				if(umin(d[y += 2*n], od)){
					pq.emplace(d[y], y);
				}
			}
		}

		for(auto [y, e] : g[x]){
			if(zx >= n) y += 3*n;
			if(umin(d[y], od + e)){
				pq.emplace(d[y], y);
			}
		}
	}

	cout << min({d[v], d[v+n], d[v+2*n], d[v+3*n]}) << '\n';


}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

		solve();
}

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