Skip to Content
CTRL K

Moving to the Capital

Pista 1

Después de precalcular todas las distancias desde la capital, consideremos dos tipos de aristas: aristas que van de nodos de menor distancia a nodos de mayor distancia desde la capital, y aristas que van de mayor a menor (o igual) distancia. Intentemos escribir una recurrencia de DP para cada tipo de arista.

Pista 2

¿Cómo deberíamos ordenar los nodos para que los hijos relevantes de cada nodo tengan sus valores de DP calculados antes que él?

Respuesta a la pista 2

Hay que procesar los nodos en orden descendente de distancia desde la capital.

Explicación

Sea distdist las distancias desde la capital para cada nodo, y dpdp lo más cerca que cada nodo puede llegar a la capital. Para un nodo dado, la relación de DP es:

  1. dp[u]=min(dp[u],dp[v])dp[u] = min(dp[u], dp[v]), si dist[u]<dist[v]dist[u] < dist[v].
  2. dp[u]=min(dp[u],dist[v])dp[u] = min(dp[u], dist[v]), si dist[u]≥dist[v]dist[u] \ge dist[v].

Como la única vez que el valor de dp[u]dp[u] depende de sus hijos es cuando dist[u]<dist[v]dist[u] < dist[v], hay que procesar los nodos en orden descendente de distancia desde la capital.

Implementación

Complejidad temporal: O(Nlog⁡N)\mathcal{O}(N\log{N})

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int test_num;
	cin >> test_num;
	for (int tc = 0; tc < test_num; tc++) {
		int n, m;
		cin >> n >> m;
		vector<vector<int>> adj(n);
		for (int i = 0; i < m; i++) {
			int u, v;
			cin >> u >> v;
			u--, v--;
			adj[u].push_back(v);
		}
 
		// calculate distance from the capital
		vector<int> capital_dist(n, -1);
		queue<array<int, 2>> q;
		q.push({0, 0});
		while (!q.empty()) {
			auto [u, t] = q.front();
			q.pop();
			if (capital_dist[u] != -1) { continue; }
			capital_dist[u] = t;
			for (int v : adj[u]) {
				if (capital_dist[v] == -1) { q.push({v, t + 1}); }
			}
		}
 
		// order the nodes by distance from capital
		vector<int> order(n);
		iota(begin(order), end(order), 0);
		sort(begin(order), end(order),
		     [&](int i, int j) { return capital_dist[i] > capital_dist[j]; });
 
		// calculate the DP
		vector<int> min_dist = capital_dist;
		for (int node1 : order) {
			for (int node2 : adj[node1]) {
				if (capital_dist[node1] < capital_dist[node2]) {
					min_dist[node1] = min(min_dist[node1], min_dist[node2]);
				} else {
					min_dist[node1] = min(min_dist[node1], capital_dist[node2]);
				}
			}
		}
 
		for (int i = 0; i < n; i++) { cout << min_dist[i] << " \n"[i == n - 1]; }
	}
}
Fundamentos