oj.uz

Submission #944845

# Submission time Handle Problem Language Result Execution time Memory
944845 2024-03-13T06:39:14 Z Amaarsaa Commuter Pass (JOI18_commuter_pass) C++14
0 / 100
 300 ms 23956 KB 
#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, X;
	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();
		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;
	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]);
				}
					
			}
		}
	}
	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];
	}
	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.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 23956 KB Output is correct
2 Correct 269 ms 22792 KB Output is correct
3 Incorrect 272 ms 22636 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 23024 KB Output is correct
2 Incorrect 286 ms 23088 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 11608 KB Output is correct
2 Correct 2 ms 10332 KB Output is correct
3 Incorrect 3 ms 10328 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 23956 KB Output is correct
2 Correct 269 ms 22792 KB Output is correct
3 Incorrect 272 ms 22636 KB Output isn't correct
4 Halted 0 ms 0 KB -