Submission #944850

#	Time	Username	Problem	Language	Result	Execution time	Memory
944850		Amaarsaa	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	355 ms	24008 KiB

commuter_pass

#include<bits/stdc++.h>
 
using namespace std;
using ll = long long ;
using pll = pair < ll, ll >;
vector < pll > adj[100005];
ll cnt = 0;
ll D[5][100005], Used[100005] = {0};
 
void Djik(ll s) {
	ll x, i, X;
	for (i = 1; i <= 100000; i ++) Used[i] = 0, D[cnt][i] = 1e18;
	priority_queue < pll, vector < pll > , greater < pll > > pq;
	D[cnt][s] = 0;
	pq.push({0, s});
	while(!pq.empty()) {
		x = pq.top().second;
		pq.pop();
		if ( Used[x]) continue;
		Used[x] =1;
		for ( pll P : adj[x]) {
			X = P.first;
			if ( D[cnt][X] > D[cnt][x] + P.second) {
				D[cnt][X] = D[cnt][x] + P.second;
				pq.push({D[cnt][X], X});
			}
		}
		
	}
	
}
ll D1[100005], D2[100005], d1[100005], d2[100005];
int main() {
	ll n, m , s, t, u, ans, v, i, x, y, c, j;
	
	cin >> n >> m >> s >> t >> u >> v;
	
	for (i = 1; i <= m; i ++) {
		cin >> x >> y >> c;
		adj[x].push_back({y, c});
		adj[y].push_back({x, c});
	}
	for (i = 1; i <= 4; i ++) for (j = 1; j <= n; j ++) D[i][j] = 1e18;
	cnt ++;
	Djik(u);
	cnt ++;
	Djik(v);
	cnt ++;
	ll X;
	priority_queue < pll, vector < pll > , greater < pll > > pq;
		for (i = 1; i <= 100000; i ++) Used[i] = 0, D[cnt][i] = 1e18;
	D[cnt][s] = 0;
	ans = D[1][v];
	for (i = 1; i <= n; i ++) {
		d1[i] = 1e18;
		d2[i] = 1e18;
		D1[i] = D[1][i];
		D2[i] = D[2][i];
	}

	d1[s] = D1[s];
	d2[s] = D2[s];
	pq.push({0, s});
	while(!pq.empty()) {
		x = pq.top().second;
		pq.pop();
		if ( Used[x] == 1) continue;
		Used[x] = 1;
		
		for ( pll P : adj[x]) {
			X = P.first;
			if ( D[cnt][X] > D[cnt][x] + P.second) {
				D[cnt][X] = D[cnt][x] + P.second;
				d1[X] = min(d1[x], D1[X]);
				d2[X] = min(d2[x], D2[X]);
				pq.push({D[cnt][X], X});
			}
			else {
				if ( min(D1[X], d1[x]) + min(D2[X], d2[x]) < d1[X] + d2[X]) {
					d1[X] =  min(D1[X], d1[x]);
					d2[X] = min(D2[X], d2[x]);
				}
					
			}
		}
	}
	//cout << ans << endl;
	cnt ++;
	for (i = 1; i <= 100000; i ++) Used[i] = 0, D[cnt][i] = 1e18;
	ans = min(ans, d1[t] + d2[t]);
	swap(s, t);
	for (i = 1; i <= n; i ++) {
		d1[i] = 1e18;
		d2[i] = 1e18;
		D1[i] = D[1][i];
		D2[i] = D[2][i];
	}
	D[cnt][s] = 0;
	d1[s] = D1[s];
	d2[s] = D2[s];
	pq.push({0, s});
	while(!pq.empty()) {
		x = pq.top().second;
		pq.pop();
		if ( Used[x] == 1) continue;
		Used[x] = 1;
		
		for ( pll P : adj[x]) {
			X = P.first;
			if ( D[cnt][X] > D[cnt][x] + P.second) {
				D[cnt][X] = D[cnt][x] + P.second;
				d1[X] = min(d1[x], D1[X]);
				d2[X] = min(d2[x], D2[X]);
				pq.push({D[cnt][X], X});
			}
			else {
				if ( min(D1[X], d1[x]) + min(D2[X], d2[x]) <= d1[X] + d2[X]) {
					d1[X] =  min(D1[X], d1[x]);
					d2[X] = min(D2[X], d2[x]);
				}
					
			}
		}
	}
	ans = min(ans, d1[t] + d2[t]);
	cout << ans << endl;
	
	
}

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