Submission #416946

#	Time	Username	Problem	Language	Result	Execution time	Memory
416946		DEQK	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	775 ms	22100 KiB

commuter_pass

#include <bits/stdc++.h>

#define ll long long
using namespace std;
const int N = 100100;
vector<pair<int, int>> g[N];
void dkstr(int u, vector<ll> &d) {
	set<pair<ll, int>> s;
	fill(d.begin(), d.end(), 1e15);
	d[u] = 0;
	s.insert({0, u});
	while(!s.empty()) {
		int v = s.begin() -> second;
		ll f = s.begin() -> first;
		s.erase(s.begin());
		if(d[v] != f) continue; 
		for(auto to : g[v]) {
			if(d[to.first] > d[v] + to.second) {
				d[to.first] = d[v] + to.second;
				s.insert({d[to.first], to.first});
			}
		}
	}
}
int main() {
	int n, m, s, t, u, v; cin >> n >> m;
	cin >> s >> t >> u >> v;
	for(int i = 1; i <= m; i++) {
		int x, y, w; cin >> x >> y >> w;
		g[x].emplace_back(y, w);
		g[y].emplace_back(x, w);
	}
	vector<ll> fs(n + 1), ft(n + 1), fu(n + 1), fv(n + 1);
	dkstr(s, fs);
	dkstr(t, ft);
	dkstr(u, fu);
	dkstr(v, fv);
	ll ans = fu[v];
	for(int it = 0; it < 2; it++) {
		vector<ll> mn(n + 1, 1e15), f(n + 1, 1e15);
		set<pair<ll, int>> d;
		d.insert({0, s});
		f[s] = 0;
		mn[s] = fu[s];
		while(!d.empty()) {
			int x = d.begin() -> second;
			ll y = d.begin() -> first;
			d.erase(d.begin());
			if(f[x] != y) continue;
			ans = min(ans, mn[x] + fv[x]);
			for(auto to : g[x]) {
				if(fs[to.first] + ft[to.first] == fs[t]) {
					mn[to.first] = min(mn[to.first], min(mn[x], fu[to.first]));
					if(f[to.first] > to.second + y) {
						f[to.first] = to.second + y;
						d.insert({f[to.first], to.first});
					}
				}
			}
		}
		swap(fu, fv);
	}
	cout << ans;
}

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