Submission #1085838

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085838		ssitaram	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	242 ms	26416 KiB

commuter_pass

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

typedef long long ll;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m; cin >> n >> m;
	int s, t; cin >> s >> t;
	int u, v; cin >> u >> v;
	--s; --t; --u; --v;
	vector<vector<pair<int, int>>> adj(n);
	while (m--) {
		int a, b, c; cin >> a >> b >> c;
		adj[--a].push_back({--b, c});
		adj[b].push_back({a, c});
	}
	vector<ll> toU(n, INT64_MAX), toV(n, INT64_MAX);
	{
		priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
		pq.push({0, u});
		while (!pq.empty()) {
			ll d = pq.top().first;
			int node = pq.top().second;
			pq.pop();
			if (toU[node] != INT64_MAX) continue;
			toU[node] = d;
			for (pair<int, int>& edge : adj[node]) {
				pq.push({d + edge.second, edge.first});
			}
		}
	}
	{
		priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
		pq.push({0, v});
		while (!pq.empty()) {
			ll d = pq.top().first;
			int node = pq.top().second;
			pq.pop();
			if (toV[node] != INT64_MAX) continue;
			toV[node] = d;
			for (pair<int, int>& edge : adj[node]) {
				pq.push({d + edge.second, edge.first});
			}
		}
	}
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
	pq.push({0, s});
	vector<vector<pair<ll, ll>>> states(n);
	auto add = [&](int node, pair<ll, ll> state) -> void {
		if (states[node].empty()) {
			for (int i = 0; i < 3; ++i) {
				states[node].push_back(state);
			}
			return;
		}
		if ((state.first < states[node][0].first) || (state.first == states[node][0].first && state.second < states[node][0].second)) {
			states[node][0] = state;
		}
		if ((state.second < states[node][1].second) || (state.second == states[node][1].second && state.first < states[node][1].first)) {
			states[node][1] = state;
		}
		if (state.first + state.second < states[node][2].first + states[node][2].second) {
			states[node][2] = state;
		}
	};
	add(s, {toU[s], toV[s]});
	vector<ll> best(n, INT64_MAX);
	vector<bool> vis(n);
	while (!pq.empty()) {
		ll d = pq.top().first;
		int node = pq.top().second;
		pq.pop();
		if (vis[node]) continue;
		vis[node] = true;
		if (node == t) {
			cout << min(toU[v], states[node][2].first + states[node][2].second) << '\n';
			return 0;
		}
		for (int i = 0; i < 3; ++i) {
			states[node][i].first = min(states[node][i].first, toU[node]);
			states[node][i].second = min(states[node][i].second, toV[node]);
		}
		for (pair<int, int>& edge : adj[node]) {
			if (d + edge.second < best[edge.first]) {
				best[edge.first] = d + edge.second;
				states[edge.first].clear();
				pq.push({d + edge.second, edge.first});
			}
			for (int i = 0; i < 3; ++i) {
				if (d + edge.second == best[edge.first]) {
					add(edge.first, states[node][i]);
				}
			}
		}
	}
	return 0;
}

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