제출 #210473

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
210473		islingr	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	661 ms	23348 KiB

commuter_pass

#include <cassert>
#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 = long long;
using vi = vector<int>;
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();
		it[u] = nullptr;
		trav(e, g[u]) {
			if (ckmin(dist[e.ff], dist[u] + e.ss)) {
				assert(it[e.ff] != nullptr);
				q.modify(it[e.ff], {dist[e.ff], e.ff});
			}
		}
	}
	return dist;
}

ll dp[2][N];
vl sd, dist[2];

pll dfs(int u) {
	if (dp[0][u] == inf) {
		assert(dp[1][u] == inf);
		dp[0][u] = dist[0][u];
		dp[1][u] = dist[1][u];
		trav(e, g[u]) {
			if (sd[u] < sd[e.ff] + e.ss) continue;
			assert(sd[u] == sd[e.ff] + e.ss);
			auto nxt = dfs(e.ff);
			if (dist[0][u] + nxt.ss < dp[0][u] + dp[1][u])
				dp[0][u] = dist[0][u], dp[1][u] = nxt.ss;
			if (dist[1][u] + nxt.ff < dp[0][u] + dp[1][u])
				dp[1][u] = dist[1][u], dp[0][u] = nxt.ff;
			if (nxt.ff + nxt.ss < dp[0][u] + dp[1][u])
				dp[0][u] = nxt.ff, dp[1][u] = nxt.ss;
		}
	}
	assert(dp[1][u] != inf);
	return {dp[0][u], dp[1][u]};
}

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

	int m;
	cin >> n >> m;
	int s, t; cin >> s >> t; --s, --t;	
	int x, y; cin >> x >> y; --x, --y;
	rep(i, 0, m) {
		int a, b, c; cin >> a >> b >> c;
		--a; --b;
		g[a].eb(b, c);
		g[b].eb(a, c);
	}

	sd = dij(s);
	dist[0] = dij(x);
	dist[1] = dij(y);
	
	assert(dist[0][y] == dist[1][x]);
	ll ans = dist[0][y];
	rep(u, 0, n) dp[0][u] = dp[1][u] = inf;
	auto tmp = dfs(t);
	ckmin(ans, tmp.ff + tmp.ss);
	cout << ans;
}

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