Submission #210514

#	Time	Username	Problem	Language	Result	Execution time	Memory
210514		islingr	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	637 ms	23268 KiB

commuter_pass

#include <iostream>
#include <vector>

using namespace std;

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define trav(x, v) for (auto &x : v)

#define eb(x...) emplace_back(x)
#define ff first
#define ss second

using ll = int64_t;
using vl = vector<ll>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;

template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

const int N = 1 << 17;
const ll inf = 1e18;
vector<pii> g[N];

#include <ext/pb_ds/priority_queue.hpp>
using namespace __gnu_pbds;
using pq = __gnu_pbds::priority_queue<pli, greater<pli>, thin_heap_tag>;

int n;

vl dij(int s) {
	vl dist(n, inf); dist[s] = 0; pq q;
	vector<pq::point_iterator> it(n);
	rep(i, 0, n) it[i] = q.push({dist[i], i});
	while (!q.empty()) {
		int u = q.top().ss; q.pop();
		trav(e, g[u])
			if (ckmin(dist[e.ff], dist[u] + e.ss))
				q.modify(it[e.ff], {dist[e.ff], e.ff});
	}
	return dist;
}

ll mx[N], my[N];
vl ds, dx, dy;

pll dfs(int u) {
	if (mx[u] == inf) {
		mx[u] = dx[u]; my[u] = dy[u];
		trav(e, g[u]) {
			if (ds[u] < ds[e.ff] + e.ss) continue;
			auto dv = dfs(e.ff);
			if (dx[u] + dv.ss < mx[u] + my[u])
				mx[u] = dx[u], my[u] = dv.ss;
			if (dv.ff + dy[u] < mx[u] + my[u])
				mx[u] = dv.ff, my[u] = dy[u];
			if (dv.ff + dv.ss < mx[u] + my[u])
				mx[u] = dv.ff, my[u] = dv.ss;
		}
	}
	return {mx[u], my[u]};
}

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

	int m, s, t, x, y; cin >> n >> m >> s >> t >> x >> y; --s; --t; --x; --y;
	while (m--) {
		int u, v, w; cin >> u >> v >> w; --u; --v;
		g[u].eb(v, w); g[v].eb(u, w);
	}
	ds = dij(s); dx = dij(x); dy = dij(y);
	rep(u, 0, n) mx[u] = my[u] = inf;
	cout << min(dx[y], dfs(t).ff + dfs(t).ss);
}

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