Submission #228436

#	Time	Username	Problem	Language	Result	Execution time	Memory
228436		pavement	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	518 ms	38380 KiB

commuter_pass

#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;
#ifdef TEST
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define ins insert
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define pf push_front
#define pp pop
#define ppb pop_back
#define ppf pop_front
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long double ld;
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tree<pair<int, int>, null_type, less<pair<int, int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int N, M, S, T, U, V, a, d, O = LLONG_MAX, distS[100005], distT[100005], distU[100005], distV[100005], ret[100005], ret2[100005];
bool vis[100005], vis2[100005];
vector<ii> adj[100005];
vector<int> nadj[100005], n2adj[100005];
iii ed[200005];
priority_queue<ii, vector<ii>, greater<ii> > pq;

int dfs(int n) {
	if (vis[n]) return ret[n];
	vis[n] = 1;
	ret[n] = distU[n];
	for (auto u : nadj[n])
		ret[n] = min(ret[n], dfs(u));
	return ret[n];
}

int dfs2(int n) {
	if (vis2[n]) return ret2[n];
	vis2[n] = 1;
	ret2[n] = distV[n];
	for (auto u : nadj[n])
		ret2[n] = min(ret2[n], dfs2(u));
	return ret2[n];
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M >> S >> T >> U >> V;
	for (int A, B, C, i = 1; i <= M; i++) {
		cin >> A >> B >> C;
		adj[A].eb(B, C);
		adj[B].eb(A, C);
		ed[i] = mt(A, B, C);
	}
	memset(distS, 127, sizeof distS);
	memset(distT, 127, sizeof distT);
	memset(distU, 127, sizeof distU);
	memset(distV, 127, sizeof distV);
	distS[S] = 0;
	pq.emplace(0, S);
	while (!pq.empty()) {
		d = pq.top().first, a = pq.top().second;
		pq.pop();
		if (d > distS[a]) continue;
		for (auto u : adj[a])
			if (distS[u.first] > d + u.second) {
				distS[u.first] = d + u.second;
				pq.emplace(distS[u.first], u.first);
			}
	}
	distT[T] = 0;
	pq.emplace(0, T);
	while (!pq.empty()) {
		d = pq.top().first, a = pq.top().second;
		pq.pop();
		if (d > distT[a]) continue;
		for (auto u : adj[a])
			if (distT[u.first] > d + u.second) {
				distT[u.first] = d + u.second;
				pq.emplace(distT[u.first], u.first);
			}
	}
	distU[U] = 0;
	pq.emplace(0, U);
	while (!pq.empty()) {
		d = pq.top().first, a = pq.top().second;
		pq.pop();
		if (d > distU[a]) continue;
		for (auto u : adj[a])
			if (distU[u.first] > d + u.second) {
				distU[u.first] = d + u.second;
				pq.emplace(distU[u.first], u.first);
			}
	}
	distV[V] = 0;
	pq.emplace(0, V);
	while (!pq.empty()) {
		d = pq.top().first, a = pq.top().second;
		pq.pop();
		if (d > distV[a]) continue;
		for (auto u : adj[a])
			if (distV[u.first] > d + u.second) {
				distV[u.first] = d + u.second;
				pq.emplace(distV[u.first], u.first);
			}
	}
	for (int A, B, C, i = 1; i <= M; i++) {
		tie(A, B, C) = ed[i];
		if (distT[B] + distS[A] + C == distS[T]) {
			nadj[A].pb(B);
			n2adj[B].pb(A);
		}
		swap(A, B);
		if (distT[B] + distS[A] + C == distS[T]) {
			nadj[A].pb(B);
			n2adj[B].pb(A);
		}
	}
	for (int i = 1; i <= N; i++) {
		int M = 1e16;
		for (int j : nadj[i]) M = min(M, dfs(j));
		O = min(O, M + distV[i]);
		M = 1e16;
		for (int j : nadj[i]) M = min(M, dfs2(j));
		O = min(O, M + distU[i]);
	}
	for (int i = 1; i <= N; i++)
		nadj[i] = n2adj[i];
	memset(vis, 0, sizeof vis);
	memset(vis2, 0, sizeof vis2);
	for (int i = 1; i <= N; i++) {
		int M = 1e16;
		for (int j : nadj[i]) M = min(M, dfs(j));
		O = min(O, M + distV[i]);
		M = 1e16;
		for (int j : nadj[i]) M = min(M, dfs2(j));
		O = min(O, M + distU[i]);
	}
	cout << min(O, distU[V]) << '\n';
}

Compilation message (stderr)

commuter_pass.cpp:55:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

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