Submission #97833

#	Time	Username	Problem	Language	Result	Execution time	Memory
97833		Anai	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	351 ms	17504 KiB

commuter_pass

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

using i64 = long long;
using pii = pair<int, int>;
using pll = pair<i64, i64>;

const int N = 1e5 + 5;

vector<pii> g[N];
vector<int> dag[N];
i64 dist[N], dist_fst[N], dist_snd[N], dp[N][4];
int reach[N], in_deg[N];

vector<int> topsort;
int n, m, src, snk, fst, snd;


static void dijkstra(int nod, i64 dist[N]) {
	priority_queue<pll> pq;

	memset(dist, 0x3f, N * sizeof(i64));
	dist[nod] = 0;
	pq.emplace(dist[nod], nod);

	while (!pq.empty()) {
		i64 dst = -pq.top().x;
		int u = pq.top().y;

		pq.pop();
		if (dst != dist[u])
			continue;

		for (auto v: g[u]) if (dist[v.x] > dst + v.y) {
			dist[v.x] = dst + v.y;
			pq.emplace(-dist[v.x], v.x); } } }

static void get_dp() {
	vector<int> srt(n);


	iota(begin(srt), end(srt), 1);
	sort(begin(srt), end(srt), [&](const int &a, const int &b) {
		return dist[a] > dist[b]; });

	memset(dp, 0x3f, sizeof dp);
	dp[snk][0] = dist_fst[snk];
	dp[snk][1] = dist_fst[snk];
	dp[snk][2] = dist_snd[snk];
	dp[snk][3] = dist_fst[snk] + dist_snd[snk];

	for (auto u: srt) {
		for (auto e: g[u]) if (dist[u] + e.y == dist[e.x]) {
			int v = e.x;
			dp[u][0] = min(dp[u][0], dp[v][0]);

			dp[u][1] = min(dp[u][1], dp[v][0] + dist_fst[u]);
			dp[u][1] = min(dp[u][1], dp[v][1]);

			dp[u][2] = min(dp[u][2], dp[v][0] + dist_snd[u]);
			dp[u][2] = min(dp[u][2], dp[v][2]);

			dp[u][3] = min(dp[u][3], dp[v][0] + dist_fst[u] + dist_snd[u]);
			dp[u][3] = min(dp[u][3], dp[v][1] + dist_snd[u]);
			dp[u][3] = min(dp[u][3], dp[v][2] + dist_fst[u]);
			dp[u][3] = min(dp[u][3], dp[v][3]); } } }

int main() {
#ifdef HOME
	freopen("joi_commuter.in", "r", stdin);
	freopen("joi_commuter.out", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;
	cin >> src >> snk;
	cin >> fst >> snd;

	for (int u, v, c, i = 0; i < m; ++i) {
		cin >> u >> v >> c;
		g[u].emplace_back(v, c);
		g[v].emplace_back(u, c); }

	dijkstra(src, dist);
	dijkstra(fst, dist_fst);
	dijkstra(snd, dist_snd);
	get_dp();

	cout << min(dist_fst[snd], dp[src][3]) << '\n';

	return 0; }

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