oj.uz

Submission #944110

# Submission time Handle Problem Language Result Execution time Memory
944110 2024-03-12T08:35:09 Z Amaarsaa Commuter Pass (JOI18_commuter_pass) C++14
0 / 100
 296 ms 26284 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;
	
	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});
	}
	memset(D, 127, sizeof D);
	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 ( d1[x] + d2[x] < d1[X] + d2[X]) {
					d1[X] = d1[x];
					d2[X] = d2[x];
				}
					
			}
		}
	}
	cout << d1[t] + d2[t] << endl;
	
	
}

Compilation message

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:31:21: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
   31 |  ll n, m , s, t, u, ans, v, i, x, y, c;
      |                     ^~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 26284 KB Output is correct
2 Correct 253 ms 25092 KB Output is correct
3 Incorrect 255 ms 24764 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 25164 KB Output is correct
2 Incorrect 293 ms 24960 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 12120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 26284 KB Output is correct
2 Correct 253 ms 25092 KB Output is correct
3 Incorrect 255 ms 24764 KB Output isn't correct
4 Halted 0 ms 0 KB -