Submission #1231692

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231692		antromancap	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	194 ms	15020 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

template <class T> bool mini(T &x, const T &y) { return y < x ? x = y, 1 : 0; }
template <class T> bool maxi(T &x, const T &y) { return y > x ? x = y, 1 : 0; }

const int N = 1e5 + 1;
int n, m, S, T, U, V;
vector<pair<int, int>> adj[N];
long long d[N], f[N], f2[N], f3[N];
bool avail[N], mark[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m >> S >> T >> U >> V;
	for (int i = 1, u, v, w; i <= m; i++) {
		cin >> u >> v >> w;
		adj[u].push_back({ v, w });
		adj[v].push_back({ u, w });
	}
	priority_queue<pair<long long, int>> pq;
	memset(d, 0x3f, 8 * N);
	memset(f, 0x3f, 8 * N);
	pq.push({ d[S] = 0, S });
	while (pq.size()) {
		int u = pq.top().second;
		pq.pop();
		if (avail[u]) continue;
		avail[u] = 1;
		for (auto [v, w] : adj[u])
			if (mini(d[v], d[u] + w)) pq.push({ -d[v], v });
	}

	memset(avail, 0, N);
	queue<int> q;
	q.push(T);
	vector<int> t;
	while (q.size()) {
		int u = q.front();
		q.pop();
		if (avail[u]) continue;
		t.push_back(u);
		mark[u] = 1;
		avail[u] = 1;
		for (auto [v, w] : adj[u])
			if (d[v] + w == d[u]) q.push(v);
	}

	memset(avail, 0, N);
	pq.push({ f[U] = 0, U });
	while (pq.size()) {
		int u = pq.top().second;
		pq.pop();
		if (avail[u]) continue;
		avail[u] = 1;
		for (auto [v, w] : adj[u])
			if (mini(f[v], f[u] + w)) pq.push({ -f[v], v });
	}
	memset(f2, 0x3f, 8 * N);
	memset(f3, 0x3f, 8 * N);
	for (int u : t) {
		mini(f2[u], f[u]);
		for (auto [v, w] : adj[u])
			if (mark[v] && d[u] == d[v] + w) mini(f2[v], f2[u]);
	}
	reverse(t.begin(), t.end());
	for (int u : t) {
		mini(f3[u], f[u]);
		for (auto [v, w] : adj[u])
			if (mark[v] && d[u] + w == d[v]) mini(f3[v], f3[u]);
	}
	for (int u : t) pq.push({ -(f[u] = min(f2[u], f3[u])), u });
	memset(avail, 0, N);
	while (pq.size()) {
		int u = pq.top().second;
		pq.pop();
		if (avail[u]) continue;
		avail[u] = 1;
		for (auto [v, w] : adj[u])
			if (mini(f[v], f[u] + w)) pq.push({ -f[v], v });
	}
	cout << f[V];
}

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