Submission #228343

#	Time	Username	Problem	Language	Result	Execution time	Memory
228343		cstuart	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	475 ms	28516 KiB

commuter_pass

#define USE_MATH_DEFINES 1
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define MOD 998244353ll
#define INF 1000000000000000000ll
#define EPS 1e-9

#define getchar_unlocked _getchar_nolock
#define putchar_unlocked _putchar_nolock

typedef long long         ll;
typedef long double       ld;
typedef pair <ll,ll>      pl;
typedef tuple <ll,ll,ll>  tl;

ll N, M, S, T, U, V, D1[100005], D2[100005], C[100005][4];
vector <pl> adj[100005];
std::priority_queue <tl, vector<tl>, greater<tl> > pq;

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N >> M >> S >> T >> U >> V;
	
	for (ll i = 1; i <= M; i++) {
		ll a, b, c;
		cin >> a >> b >> c;
		adj[a].emplace_back(c, b);
		adj[b].emplace_back(c, a);
	}
	
	for (ll i = 1; i <= N; i++) {
		D1[i] = INF;
		D2[i] = INF;
		C[i][0] = INF;
		C[i][1] = INF;
		C[i][2] = INF;
		C[i][3] = INF;
	}
	
	D1[S] = 0;
	pq.emplace(0, S, -1);
	
	while (!pq.empty()) {
		ll curnode = get<1>(pq.top());
		ll curdist = get<0>(pq.top());
		pq.pop();
		if (curdist > D1[curnode]) continue;
		for (pl edge : adj[curnode]) {
			ll nexnode = edge.second;
			ll nexdist = D1[curnode] + edge.first;
			if (nexdist < D1[nexnode]) {
				D1[nexnode] = nexdist;
				pq.emplace(D1[nexnode], nexnode, -1);
			}
		}
	}
	
	D2[T] = 0;
	pq.emplace(0, T, -1);
	
	while (!pq.empty()) {
		ll curnode = get<1>(pq.top());
		ll curdist = get<0>(pq.top());
		pq.pop();
		if (curdist > D2[curnode]) continue;
		for (pl edge : adj[curnode]) {
			ll nexnode = edge.second;
			ll nexdist = D2[curnode] + edge.first;
			if (nexdist < D2[nexnode]) {
				D2[nexnode] = nexdist;
				pq.emplace(D2[nexnode], nexnode, -1);
			}
		}
	}
	
	C[U][0] = 0;
	pq.emplace(0, U, 0);
	
	while (!pq.empty()) {
		ll curnode = get<1>(pq.top());
		ll curdist = get<0>(pq.top());
		ll state   = get<2>(pq.top());
		pq.pop();
		if (curdist > C[curnode][state]) continue;
		for (pl edge : adj[curnode]) {
			ll nexnode = edge.second;
			ll edgewgt = edge.first;
			// 0 -> 0
			if (state == 0 && C[curnode][0] + edgewgt < C[nexnode][0]) {
				C[nexnode][0] = C[curnode][0] + edgewgt;
				pq.emplace(C[nexnode][0], nexnode, 0);
			}
			// 0 or 1 -> 1
			if ((state == 0 || state == 1) && C[curnode][state] < C[nexnode][1]
			                               && D1[curnode] + edgewgt + D2[nexnode] == D1[T]) {
			    C[nexnode][1] = C[curnode][state];
				pq.emplace(C[nexnode][1], nexnode, 1);                           	
			}
			// 0 or 2 -> 2
			if ((state == 0 || state == 2) && C[curnode][state] < C[nexnode][2]
			                               && D2[curnode] + edgewgt + D1[nexnode] == D1[T]) {
			    C[nexnode][2] = C[curnode][state];
				pq.emplace(C[nexnode][2], nexnode, 2);
			}
			// 1 or 2 or 3 -> 3
			if (state != 0 && C[curnode][state] + edgewgt < C[nexnode][3]) {
				C[nexnode][3] = C[curnode][state] + edgewgt;
				pq.emplace(C[nexnode][3], nexnode, 3);
			}
		}
	}
	
	cout << min(min(min(C[V][0], C[V][1]), C[V][2]), C[V][3]);
	
    return 0;
}

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