oj.uz

Submission #656187

# Submission time Handle Problem Language Result Execution time Memory
656187 2022-11-06T13:07:06 Z BlancaHM Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 537 ms 29376 KB 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long int ll;

ll inf = 1e18;
vector<vector<pair<int, int>>> adjList;
vector<vector<int>> DAG1, DAG2; // listas inversas de adyacencia
vector<ll> dist_desde_u, dist_hasta_v, dp_u1, dp_u2, dp_v1, dp_v2;

int n, s, t, u, v;

void dijkstra(int salida, vector<ll> & dist) {
	dist.assign(n, inf);
	priority_queue<pair<ll, int>> pq;
	pq.push(make_pair(0, salida));
	dist[salida] = 0;
	while(!pq.empty()) {
		ll distNodo = -pq.top().first;
		int nodo = pq.top().second;
		pq.pop();
		if (dist[nodo] < distNodo) continue;
		for (auto vecino: adjList[nodo]) {
			int nodoVecino = vecino.first;
			ll coste = vecino.second;
			if (distNodo + coste < dist[nodoVecino]) {
				dist[nodoVecino] = distNodo + coste;
				pq.push(make_pair(-dist[nodoVecino], nodoVecino));
			}
		}
	}
}

// coste minimo en llegar desde u al nodo

ll calcDPu1(int nodo) {
	if (dp_u1[nodo] != -1) return dp_u1[nodo];
	ll ans = dist_desde_u[nodo];
	for (int padre: DAG1[nodo]) {
		ans = min(ans, calcDPu1(padre));
	}
	return dp_u1[nodo] = ans;
}

ll calcDPu2(int nodo) {
	if (dp_u2[nodo] != -1) return dp_u2[nodo];
	ll ans = dist_desde_u[nodo];
	for (int padre: DAG2[nodo]) {
		ans = min(ans, calcDPu2(padre));
	}
	return dp_u2[nodo] = ans;
}

// coste minimo en llegar desde v al nodo
ll calcDPv1(int nodo) {
	if (dp_v1[nodo] != -1) return dp_v1[nodo];
	ll ans = dist_hasta_v[nodo];
	for (int padre: DAG1[nodo]) {
		ans = min(ans, calcDPv1(padre));
	}
	return dp_v1[nodo] = ans;
}

ll calcDPv2(int nodo) {
	if (dp_v2[nodo] != -1) return dp_v2[nodo];
	ll ans = dist_hasta_v[nodo];
	for (int padre: DAG2[nodo]) {
		ans = min(ans, calcDPv2(padre));
	}
	return dp_v2[nodo] = ans;
}

ll minDist() {
	vector<ll> dist_desde_s, dist_hasta_t;
	dijkstra(s, dist_desde_s);
	dijkstra(t, dist_hasta_t);
	ll distanciaMasCorta = dist_desde_s[t];
	DAG1.assign(n, vector<int>());
	DAG2.assign(n, vector<int>());
	for (int nodo = 0; nodo < n; nodo++) {
		for (auto arista: adjList[nodo]) {
			int vecino = arista.first;
			ll coste = arista.second;
			if (dist_desde_s[nodo] + coste + dist_hasta_t[vecino] == distanciaMasCorta) {
				DAG1[vecino].push_back(nodo);
				DAG2[nodo].push_back(vecino);
				//cout << "added " << nodo+1 << ' ' << vecino+1 << endl;
			}
		}
	}
	dijkstra(u, dist_desde_u);
	dijkstra(v, dist_hasta_v);
	ll ans = dist_desde_u[v];
	dp_u1.assign(n, -1);
	dp_u2.assign(n, -1);
	dp_v1.assign(n, -1);
	dp_v2.assign(n, -1);
	for (int nodo = 0; nodo < n; nodo++) {
		if (DAG1[nodo].size() + DAG2[nodo].size()) {
			ans = min(ans, min(calcDPu1(nodo) + calcDPv2(nodo), calcDPu2(nodo) + calcDPv1(nodo)));
			/*cout << nodo+1 << ' ' << calcDPu1(nodo) << ' ' << calcDPu2(nodo) << ' ';
			cout << calcDPv1(nodo) <<' ' << calcDPv2(nodo) << endl;*/
		}
	}
	return ans;
}

int main() {
	int m, a, b, c;
	cin >> n >> m;
	adjList.assign(n, vector<pair<int, int>>());
	cin >> s >> t;
	cin >> u >> v;
	s--;
	t--;
	u--;
	v--;
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		adjList[a-1].push_back(make_pair(b-1, c));
		adjList[b-1].push_back(make_pair(a-1, c));
	}
	cout << minDist() << '\n';
	return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 19888 KB Output is correct
2 Correct 473 ms 21292 KB Output is correct
3 Correct 537 ms 25172 KB Output is correct
4 Correct 427 ms 19772 KB Output is correct
5 Correct 441 ms 22640 KB Output is correct
6 Correct 412 ms 19868 KB Output is correct
7 Correct 450 ms 23316 KB Output is correct
8 Correct 377 ms 22708 KB Output is correct
9 Correct 369 ms 19828 KB Output is correct
10 Correct 329 ms 19836 KB Output is correct
11 Correct 231 ms 21080 KB Output is correct
12 Correct 417 ms 19812 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 437 ms 22232 KB Output is correct
2 Correct 383 ms 22364 KB Output is correct
3 Correct 410 ms 22204 KB Output is correct
4 Correct 404 ms 22560 KB Output is correct
5 Correct 406 ms 26204 KB Output is correct
6 Correct 406 ms 29072 KB Output is correct
7 Correct 422 ms 29376 KB Output is correct
8 Correct 411 ms 25552 KB Output is correct
9 Correct 394 ms 26292 KB Output is correct
10 Correct 384 ms 25604 KB Output is correct
11 Correct 198 ms 25272 KB Output is correct
12 Correct 411 ms 28956 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1052 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 34 ms 2356 KB Output is correct
5 Correct 18 ms 1396 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 3 ms 368 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 17 ms 1336 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 320 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 312 KB Output is correct
15 Correct 2 ms 340 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 19888 KB Output is correct
2 Correct 473 ms 21292 KB Output is correct
3 Correct 537 ms 25172 KB Output is correct
4 Correct 427 ms 19772 KB Output is correct
5 Correct 441 ms 22640 KB Output is correct
6 Correct 412 ms 19868 KB Output is correct
7 Correct 450 ms 23316 KB Output is correct
8 Correct 377 ms 22708 KB Output is correct
9 Correct 369 ms 19828 KB Output is correct
10 Correct 329 ms 19836 KB Output is correct
11 Correct 231 ms 21080 KB Output is correct
12 Correct 417 ms 19812 KB Output is correct
13 Correct 437 ms 22232 KB Output is correct
14 Correct 383 ms 22364 KB Output is correct
15 Correct 410 ms 22204 KB Output is correct
16 Correct 404 ms 22560 KB Output is correct
17 Correct 406 ms 26204 KB Output is correct
18 Correct 406 ms 29072 KB Output is correct
19 Correct 422 ms 29376 KB Output is correct
20 Correct 411 ms 25552 KB Output is correct
21 Correct 394 ms 26292 KB Output is correct
22 Correct 384 ms 25604 KB Output is correct
23 Correct 198 ms 25272 KB Output is correct
24 Correct 411 ms 28956 KB Output is correct
25 Correct 20 ms 1052 KB Output is correct
26 Correct 1 ms 312 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 34 ms 2356 KB Output is correct
29 Correct 18 ms 1396 KB Output is correct
30 Correct 2 ms 340 KB Output is correct
31 Correct 3 ms 368 KB Output is correct
32 Correct 4 ms 468 KB Output is correct
33 Correct 2 ms 340 KB Output is correct
34 Correct 17 ms 1336 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 320 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 1 ms 312 KB Output is correct
39 Correct 2 ms 340 KB Output is correct
40 Correct 379 ms 24180 KB Output is correct
41 Correct 358 ms 23964 KB Output is correct
42 Correct 397 ms 24056 KB Output is correct
43 Correct 292 ms 27096 KB Output is correct
44 Correct 258 ms 27368 KB Output is correct
45 Correct 440 ms 29108 KB Output is correct
46 Correct 466 ms 29116 KB Output is correct
47 Correct 414 ms 23604 KB Output is correct
48 Correct 228 ms 25456 KB Output is correct
49 Correct 369 ms 23712 KB Output is correct
50 Correct 444 ms 27852 KB Output is correct
51 Correct 431 ms 29168 KB Output is correct