Submission #1130288

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130288		lucaskojima	Commuter Pass (JOI18_commuter_pass)	C++17	16 / 100	190 ms	18640 KiB

commuter_pass

// subtask 1
#include "bits/stdc++.h"
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const char nl = '\n';
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;

int main() {
	ios::sync_with_stdio(0), cin.tie(0);

	int n, m; cin >> n >> m;
	int _, x; cin >> _ >> x;
	int ini, fim; cin >> ini >> fim;

	using pll = pair<ll, ll>;
	vector<vector<pll>> adj(n + 1);

	for (int i = 0; i < m; i++) {
		int a, b; ll c; cin >> a >> b >> c;
		adj[a].push_back({b, c});
		adj[b].push_back({a, c});
	}

	vector<vector<ll>> dist(3, vector<ll>(n + 1));

	auto dijkstra = [&](int s, int t) -> void {
		fill(all(dist[t]), LINF);

		priority_queue<pll, vector<pll>, greater<pll>> pq;
		pq.push({0, s}); dist[t][s] = 0;

		while (!pq.empty()) {
			auto [d, x] = pq.top(); pq.pop();
			if (dist[t][x] != d) continue;

			for (auto [k, dd] : adj[x]) {
				if (d + dd < dist[t][k]) {
					dist[t][k] = d + dd;
					pq.push({dist[t][k], k});
				}
			}
		}
	};

	dijkstra(ini, 0);
	dijkstra(fim, 1);
	dijkstra(x, 2);

	auto ini_x = [&](int k) -> bool {
		return dist[0][k] + dist[2][k] == dist[0][x];
	};

	ll ans = LINF;
	for (int i = 1; i <= n; i++)
		if (ini_x(i))
			ans = min(ans, dist[1][i]);

	cout << ans << nl;
	return 0;
}

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