Submission #1210201

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210201		kian2009	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	288 ms	24700 KiB

commuter_pass

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

typedef long long ll;
typedef pair<ll, ll> pll;

const int MAXN = 2e5 + 10;
const ll INF = 4e18;

ll n, m, s, t, s1, e1, h[4][MAXN], dp1[MAXN], dp2[MAXN];
vector<int> num;
bool seen[4][MAXN];
vector<pll> adj[MAXN];

void input() {
	cin >> n >> m >> s >> t >> s1 >> e1;
	for (int i = 0; i < m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		adj[x].push_back({y, z});
		adj[y].push_back({x, z});
	}
}

void dij1(int c) {
	priority_queue<pll, vector<pll>, greater<pll>> q;
	if (c == 0) 
		q.push({0, s});
	else if (c == 1)
		q.push({0, s1});
	else if (c == 2)
		q.push({0, e1});
	else
		q.push({0, t});
	while (!q.empty()) {
		ll u = q.top().second, d = q.top().first;
		q.pop();
		if (!seen[c][u]) {
			if (c == 0)
				num.push_back(u);
			seen[c][u] = true;
			h[c][u] = d;
			for (auto p : adj[u]) {
				int v = p.first, w = p.second;
				if (!seen[c][v])
					q.push({d + w, v});	
			}
		}
	}
}

void calcDp() {
	for (auto u : num) {
		dp1[u] = h[2][u];
		for (auto p : adj[u]) {
			int v = p.first, w = p.second;
			if ((h[0][v] + w + h[3][u]) == h[0][t])
				dp1[u] = min(dp1[u], dp1[v]);
		}
	}
	reverse(num.begin(), num.end());
	for (auto u : num) {
		dp2[u] = h[2][u];
		for (auto p : adj[u]) {
			int v = p.first, w = p.second;
			if ((h[0][u] + w + h[3][v]) == h[0][t])
				dp2[u] = min(dp2[u], dp2[v]);	
		}
	}
}

ll findAns() {
	ll res = INF;
	for (int i = 1; i <= n; i++)
		res = min(res, h[1][i] + min(dp1[i], dp2[i]));
	return res;	
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	input();
	dij1(0);
	dij1(1);
	dij1(2);
	dij1(3);
	calcDp();
	cout << findAns() << endl;
	return 0;	
}

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