Submission #1274048

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274048		crispxx	Commuter Pass (JOI18_commuter_pass)	C++20	55 / 100	290 ms	20184 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--;
	
	if(n <= 300) {
		vector<vector<int>> d(n, vector<int>(n, inf));
		for(int i = 0; i < n; i++) d[i][i] = 0;
		
		for(int i = 0; i < m; i++) {
			int u, v, w; cin >> u >> v >> w;
			u--, v--;
			chmin(d[u][v], w);
			chmin(d[v][u], w);
		}
		
		for(int k = 0; k < n; k++) {
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < n; j++) {
					if(d[i][k] < inf && d[k][j] < inf) {
						chmin(d[i][j], d[i][k] + d[k][j]);
					}
				}
			}
		}
		
		int ans = d[U][V];
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(d[S][i] + d[i][j] + d[j][T] == d[S][T] ) {
					chmin(ans, d[U][i] + d[j][V]);
					chmin(ans, d[U][j] + d[i][V]);
				}
			}
		}
		
		cout << ans << nl;
		return;
	}
	
	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});
	}
	
	vector<ar<int, 4>> d(n, {inf, inf, inf, inf});
	vector<int> p(n);
	
	auto D = [&](int s, int j) -> void {
		d[s][j] = 0;
		p[s] = -1;
		
		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][j]) continue;
			
			for(auto [to, w] : adj[v]) {
				if( chmin(d[to][j], d_v + w) ) {
					pq.push({d[to][j], to});
					p[to] = v;
				}
			}
		}
	};
	
	D(U, 0), D(V, 1), D(T, 3), D(S, 2);
	
	if(S == U) {
		int ans = d[V][0];
		for(int i = 0; i < n; i++) {
			if(d[i][2] + d[i][3] == d[T][0]) {
				chmin(ans, d[i][1]);
			}
		}
		cout << ans << nl;
		return;
	}
	
	vector<int> path;
	
	for(auto v = T; v != -1; v = p[v]) {
		path.pb(v);
	}
	
	int ans1 = inf, ans2 = inf;
	
	for(auto &x : path) {
		chmin(ans1, d[x][0]);
		chmin(ans2, d[x][1]);
	}
	
	int ans = d[V][0];
		
	chmin(ans, ans1 + ans2);
	
	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: 0 / 45