Submission #897185

#	Time	Username	Problem	Language	Result	Execution time	Memory
897185		aqxa	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	258 ms	23732 KiB

commuter_pass

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

using ll = long long; 

const int N = 1e5; 

vector<pair<int, ll>> g[N];
vector<ll> ds, dt, du, dv; 
int n, m, s, t, u, v; 

vector<int> ord; 

void work(vector<ll> & d, int st) {
	d[st] = 0; 
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q; 
	q.push({0, st}); 
	while (!q.empty()) {
		int x = q.top().second; 
		ll cd = q.top().first; 
		q.pop(); 
		if (d[x] < cd) continue; 
		if (st == s) ord.push_back(x); 
		for (pair<int, ll> next: g[x]) {
			ll nd = next.second + cd; 
			int nx = next.first; 
			if (nd < d[nx]) {
				d[nx] = nd; 
				q.push({nd, nx}); 
			}
		}
	}
}

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> m >> s >> t >> u >> v; 
	s--; t--; u--; v--; 
	ds = vector<ll>(n, 9e18);
	dt = vector<ll>(n, 9e18);
	du = vector<ll>(n, 9e18);
	dv = vector<ll>(n, 9e18); 
	for (int i = 0; i < m; ++i) {
		int x, y; ll w; 
		cin >> x >> y >> w; 
		x--; y--; 
		g[x].push_back({y, w}); 
		g[y].push_back({x, w}); 
	}

	work(ds, s); 
	work(dt, t); 
	work(du, u); 
	work(dv, v); 

	assert(ds[t] == dt[s]); 
	assert(du[v] == dv[u]); 

	vector<ll> dpu(n, 9e18), dpv(n, 9e18); 
	vector<int> vis(n, 0); 

	ll ans = du[v]; 

	for (auto x: ord) {
		vis[x] = 1; 
		if (ds[x] + dt[x] == ds[t]) {
			dpu[x] = du[x]; 
			dpv[x] = dv[x]; 
			for (auto last: g[x]) {
				int nd = last.first; 
				if (vis[nd] && ds[nd] + dt[nd] == ds[t]) {
					dpu[x] = min(dpu[x], dpu[nd]); 
					dpv[x] = min(dpv[x], dpv[nd]); 
				}
			}
			ans = min(ans, dpu[x] + dv[x]); 
			ans = min(ans, dpv[x] + du[x]); 
		}
	}

	cout << ans << "\n";

	return 0; 
}	

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