제출 #1231847

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1231847		antromancap	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	181 ms	19980 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

template <class T> bool mini(T &x, const T &y) { return y < x ? x = y, 1 : 0; }
template <class T> bool maxi(T &x, const T &y) { return y > x ? x = y, 1 : 0; }

const int N = 1e5 + 1;
int n, m, S, T, U, V, deg[N];
vector<pair<int, int>> adj[N];
vector<int> adj2[N];
long long dS[N], dT[N], dU[N], dV[N], f[N], g[N];
bool avail[N], mark[N];

void dijkstra(long long dist[], int s) {
	memset(avail, 0, N);
	memset(dist, 0x3f, 8 * N);
	priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;
	q.push({ dist[s] = 0, s });
	while (q.size()) {
		int u = q.top().second;
		q.pop();
		if (avail[u]) continue;
		avail[u] = 1;
		for (auto [v, w] : adj[u])
			if (mini(dist[v], dist[u] + w)) q.push({ dist[v], v });
	}
}

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

	cin >> n >> m >> S >> T >> U >> V;
	for (int i = 1, u, v, w; i <= m; i++) {
		cin >> u >> v >> w;
		adj[u].push_back({ v, w });
		adj[v].push_back({ u, w });
	}

	dijkstra(dS, S);
	dijkstra(dT, T);
	dijkstra(dU, U);
	dijkstra(dV, V);

	memset(avail, 0, N);
	memset(f, 0x3f, 8 * N);
	memset(g, 0x3f, 8 * N);
	queue<int> q;
	q.push(T);
	vector<int> t;
	while (q.size()) {
		int u = q.front();
		q.pop();
		if (avail[u]) continue;
		avail[u] = 1;
		for (auto [v, w] : adj[u])
			if (dS[v] + w + dT[u] == dS[T]) {
				q.push(v);
				deg[u]++;
				adj2[v].push_back(u);
			}
	}
	q.push(S);
	while (q.size()) {
		int u = q.front();
		q.pop();
		t.push_back(u);
		for (int v : adj2[u]) {
			deg[v]--;
			if (!deg[v]) q.push(v);
		}
	}
	long long ans = 1e18;
	for (int u : t) {
		mini(f[u], dU[u]);
		mini(g[u], dV[u]);
		mini(ans, f[u] + dV[u]);
		mini(ans, g[u] + dU[u]);
		for (int v : adj2[u]) mini(f[v], f[u]), mini(g[v], g[u]);
	}
	cout << min(dU[V], ans);
}

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