Submission #228321

#	Time	Username	Problem	Language	Result	Execution time	Memory
228321		cstuart	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	431 ms	21096 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], C1[100005], C2[100005];
vector <pl> adj[100005];
std::priority_queue <pl, vector<pl>, greater<pl> > 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;
		C1[i] = INF;
		C2[i] = INF;
	}
	
	D1[S] = 0;
	pq.emplace(0, S);
	
	while (!pq.empty()) {
		ll curnode = pq.top().second;
		ll curdist = pq.top().first;
		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);
			}
		}
	}
	
	D2[T] = 0;
	pq.emplace(0, T);
	
	while (!pq.empty()) {
		ll curnode = pq.top().second;
		ll curdist = pq.top().first;
		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);
			}
		}
	}
	
	C1[U] = 0;
	pq.emplace(0, U);
	
	while (!pq.empty()) {
		ll curnode = pq.top().second;
		ll curdist = pq.top().first;
		pq.pop();
		if (curdist > C1[curnode]) continue;
		for (pl edge : adj[curnode]) {
			ll nexnode = edge.second;
			ll nexdist;
			if (D1[curnode] + edge.first + D2[nexnode] == D1[T]) nexdist = C1[curnode];
			else nexdist = C1[curnode] + edge.first;
			if (nexdist < C1[nexnode]) {
				C1[nexnode] = nexdist;
				pq.emplace(C1[nexnode], nexnode);
			}
		}
	}
	
	C2[U] = 0;
	pq.emplace(0, U);
	
	while (!pq.empty()) {
		ll curnode = pq.top().second;
		ll curdist = pq.top().first;
		pq.pop();
		if (curdist > C2[curnode]) continue;
		for (pl edge : adj[curnode]) {
			ll nexnode = edge.second;
			ll nexdist;
			if (D2[curnode] + edge.first + D1[nexnode] == D1[T]) nexdist = C2[curnode];
			else nexdist = C2[curnode] + edge.first;
			if (nexdist < C2[nexnode]) {
				C2[nexnode] = nexdist;
				pq.emplace(C2[nexnode], nexnode);
			}
		}
	}
	
	cout << min(C1[V], C2[V]);
	
    return 0;
}

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