Submission #1130287

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130287		lucaskojima	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	297 ms	23148 KiB

commuter_pass

// subtask 2
#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 a, b; cin >> a >> b;
	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<ll> dist(n + 1);
	vector<int> pai(n + 1);
	set<pii> zero;

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

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

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

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

	dijkstra(a);

	vector<int> v = {b};
	while (v.back() != a)
		v.push_back(pai[v.back()]);
	reverse(all(v));

	for (int i = 0; i < sz(v) - 1; i++) {
		zero.insert({v[i], v[i + 1]});
		zero.insert({v[i + 1], v[i]});
	}

	dijkstra(ini);

	cout << dist[fim] << nl;
	return 0;
}

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