Submission #1274056

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274056		crispxx	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	219 ms	20988 KiB

commuter_pass

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

#define int long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define nl '\n'

template <typename A, typename B>
bool chmin(A &a, const B &b) {
	if(a > b) {
		return a = b, true;
	}
	return false;
}

template <typename A, typename B>
bool chmax(A &a, const B &b) {
	if(a < b) {
		return a = b, true;
	}
	return false;
}

const int inf = 1e18;

void solve() {
	int n, m; cin >> n >> m;
	
	int S, T, U, V; cin >> S >> T >> U >> V;
	S--, T--, U--, V--;
	
	vector<vector<ar<int, 2>>> adj(n);
	
	for(int i = 0; i < m; i++) {
		int u, v, w; cin >> u >> v >> w;
		u--, v--;
		adj[u].pb({v, w});
		adj[v].pb({u, w});
	}
	
	auto D = [&](int s, vector<int> &d) -> void {
		fill(all(d), inf);
		d[s] = 0;
		
		priority_queue<ar<int, 2>, vector<ar<int, 2>>, greater<>> pq;
		pq.push({0, s});
		
		while(!pq.empty()) {
			auto [d_v, v] = pq.top();
			pq.pop();
			
			if(d_v != d[v]) continue;
			
			for(auto [to, w] : adj[v]) {
				if( chmin(d[to], d[v] + w) ) {
					pq.push({d[to], to});
				}
			}
		}
	};
	
	vector<int> du(n), dv(n), ds(n);
	
	D(U, du), D(V, dv);
	
	vector<vector<int>> dp(2, vector<int>(n, inf));
	
	int ans = du[V];
	
	auto D2 = [&](int s, int t) -> void {
		fill(all(dp[0]), inf);
		fill(all(dp[1]), inf);
		
		dp[0][s] = du[s];
		dp[1][s] = dv[s];
		
		vector<int> d(n, inf);
		d[s] = 0;
		
		priority_queue<ar<int, 2>, vector<ar<int, 2>>, greater<>> pq;
		pq.push({0, s});
		
		while(!pq.empty()) {
			auto [d_v, v] = pq.top();
			pq.pop();
			
			if(d_v != d[v]) continue;
			
			for(auto [to, w] : adj[v]) {
				if( d[to] > d[v] + w ) {
					d[to] = d[v] + w;
					dp[0][to] = min(dp[0][v], du[to]);
					dp[1][to] = min(dp[1][v], dv[to]);
					pq.push({d[to], to});
				} else if( d[to] == d[v] + w ) {
					if( dp[0][to] + dp[1][to] > min(du[to], dp[0][v]) + min(dv[to], dp[1][v]) ) {
						dp[0][to] = min(dp[0][v], du[to]);
						dp[1][to] = min(dp[1][v], dv[to]);
					} 
				}
			}
		}
		
		chmin(ans, dp[0][t] + dp[1][t]);
	};
	
	D2(S, T), D2(T, S);
	
	cout << ans << nl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	solve();
}

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