Submission #1188714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188714		prism7k	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	331 ms	19764 KiB

commuter_pass

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

using ll = long long;
vector<vector<pair<int, int>>> adj;
vector<ll> d[3], dp[2];
const ll INF = 2e16;

int main() {
	int N, M, S, T, U, V; cin >> N >> M >> S >> T >> U >> V;
	adj.resize(N + 1);
	d[0].assign(N + 1, INF);
	d[1].assign(N + 1, INF);
	d[2].assign(N + 1, INF);
	dp[0].assign(N + 1, INF);
	dp[1].assign(N + 1, INF);
	
	for(int i = 0, u, v, w; i < M; ++i) {
		cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	
	function<void(int, int)> dj1 = [&](int start, int idx) {
		priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> q;
		vector<bool> vis(N + 1, false);
		q.push({0LL, start});
		
		while(!q.empty()) {
			auto[cur_weight, u] = q.top(); q.pop();
			if(vis[u]) continue;
			vis[u] = true;
			d[idx][u] = cur_weight;
			
			for(auto[v, w] : adj[u]) {
				q.push({cur_weight + w, v});
			}
		}
	};
	
	dj1(U, 0);
	dj1(V, 1);
	
	ll ans = d[0][V];
	
	function<void()> dj2 = [&] {
		priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<>> q;
		vector<bool> vis(N + 1, false);
		q.push({0LL, S, 0});
		
		while(!q.empty()) {
			auto[cur_weight, u, p] = q.top(); q.pop();
			
			if(!vis[u]) {
				vis[u] = true;
				d[2][u] = cur_weight;
				dp[0][u] = min(d[0][u], dp[0][p]);
				dp[1][u] = min(d[1][u], dp[1][p]);
				for(auto[v, w] : adj[u]) {
					q.push({cur_weight + w, v, u});
				}
			} else if(cur_weight == d[2][u]) {
				if(
					(min(d[0][u], dp[0][p]) +
					 min(d[1][u], dp[1][p])) <= dp[0][u] + dp[1][u]
				) {
					dp[0][u] = min(d[0][u], dp[0][p]);
					dp[1][u] = min(d[1][u], dp[1][p]);
				}
			}
		}
		
		ans = min(ans, dp[0][T] + dp[1][T]);
	};
	
	dj2();
	
	cout << ans << "\n";
}

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