oj.uz

Submission #944861

# Submission time Handle Problem Language Result Execution time Memory
944861 2024-03-13T06:49:04 Z Amaarsaa Commuter Pass (JOI18_commuter_pass) C++14
0 / 100
 339 ms 26496 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}, ans, n, d1[100005], d2[100005], D1[100005], D2[100005];
 
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});
			}
		}
		
	}
	
}
void Djik1(ll s) {
	ll i, ans, x, 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;
	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]);
				}
					
			}
		}
	}
	
}
int main() {
	ll m, u, ans, v, i, x, y, c, j, s, t;
	
	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;
	ans = D[1][v];
	Djik1(s);
	cnt ++;
	//cout << ans << endl;
	swap(s, t);
	ans = min(ans, d1[t] + d2[t]);
	Djik1(s);
	ans = min(ans, d1[t] + d2[t]);
	cnt ++;


	cout << ans << endl;
	
	
}

Compilation message

commuter_pass.cpp: In function 'void Djik1(ll)':
commuter_pass.cpp:33:8: warning: unused variable 'ans' [-Wunused-variable]
   33 |  ll i, ans, x, X;
      |        ^~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:88:5: warning: unused variable 'X' [-Wunused-variable]
   88 |  ll X;
      |     ^

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 24356 KB Output is correct
2 Incorrect 329 ms 22784 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 23172 KB Output is correct
2 Correct 339 ms 23068 KB Output is correct
3 Incorrect 323 ms 26496 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

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

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 24356 KB Output is correct
2 Incorrect 329 ms 22784 KB Output isn't correct
3 Halted 0 ms 0 KB -