Submission #927145

#	Time	Username	Problem	Language	Result	Execution time	Memory
927145		Gromp15	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	246 ms	20112 KiB

commuter_pass

#include <bits/stdc++.h>
#define ll long long
#define ar array
#define db double
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rint(l, r) uniform_int_distribution<int>(l, r)(rng)
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
void test_case() {
	int n, m;
	cin >> n >> m;
	int S, T, U, V;
	cin >> S >> T >> U >> V;
	vector<vector<ar<int, 2>>> adj(n+1);
	for (int i = 0; i < m; i++) {
		int x, y, w;
		cin >> x >> y >> w;
		adj[x].push_back({y, w});
		adj[y].push_back({x, w});
	}
	auto cost = [&](int sx) -> vector<ll> {
		vector<ll> d(n+1, 1e18);
		priority_queue<ar<ll, 2>, vector<ar<ll, 2>>, greater<ar<ll, 2>>> q;
		q.push({0, sx});
		d[sx] = 0;
		while (q.size()) {
			auto [weight, v] = q.top(); q.pop();
			if (weight != d[v]) continue;
			for (auto [u, w] : adj[v]) {
				if (ckmin(d[u], d[v] + w)) {
					q.push({d[u], u});
				}
			}
		}
		return d;
	};
	vector<ll> ds(cost(S)), dt(cost(T)), du(cost(U)), dv(cost(V));
	// sort by order of dv
	vector<int> each(n);
	iota(all(each), 1);
	sort(all(each), [&](int x, int y) { return dv[x] < dv[y]; });
	vector<int> where(n+1);
	for (int i = 0; i < n; i++) where[each[i]] = i;
	ll ans = 1e18, bst = ds[T];
	vector<int> dp1(n+1, 1e9), dp2(n+1, 1e9);
	vector<int> o1(n);
	iota(all(o1), 1);
	sort(all(o1), [&](int x, int y) { return ds[x] < ds[y]; });
	for (int v : o1) { // v --> s
		if (ds[v] + dt[v] != bst) continue;
		dp1[v] = where[v];
		for (auto [u, w] : adj[v]) {
			if (dt[v] + w + ds[u] == bst) {
				ckmin(dp1[v], dp1[u]);
			}
		}
	}
	sort(all(o1), [&](int x, int y) { return dt[x] < dt[y]; });
	for (int v : o1) { // v --> t
		if (ds[v] + dt[v] != bst) continue;
		dp2[v] = where[v];
		for (auto [u, w] : adj[v]) {
			if (ds[v] + w + dt[u] == bst) {
				ckmin(dp2[v], dp2[u]);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		int idx = min(dp1[i], dp2[i]);
		if (idx < n) {
			ckmin(ans, du[i] + dv[each[idx]]);
		}
	}
	cout << min(ans, du[V]) << '\n';
		
	
 
 
 
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
//    cin >> t;
    while (t--) test_case();
}
 

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