Submission #656187

#	Time	Username	Problem	Language	Result	Execution time	Memory
656187		BlancaHM	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	537 ms	29376 KiB

commuter_pass

#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 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45