Timeline

Análisis oficial (C++)

Construyamos un grafo y, para cada tupla $(a, b, x)$ , agreguemos una arista dirigida de $a$ a $b$ con peso $x$ . Observemos que no puede haber ciclos en este grafo, porque de lo contrario no existiría solución. Por lo tanto, podemos procesar las sesiones (tuplas) en orden usando orden topológico.

Sin pérdida de generalidad, supongamos que el orden topológico es $1, 2, \dots , N$ de modo que todas las aristas cumplen $a \lt b$ . Entonces, para cada arista dirigida en orden creciente de $a$ , asignamos $S_b = \max(S_b, S_a + x)$ , ya que la fecha más temprana posible es la posterior entre $S_b$ y $S_a + x$ .

Una vez procesadas todas las aristas, los $S_1, S_2, \dots , S_N$ resultantes son las fechas más tempranas posibles con las restricciones de aristas dadas, y terminamos.

Implementación

Complejidad temporal: $\mathcal{O}(N+M)$

C++Java


#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
 
void topo_sorting(vector<vector<pair<int, int>>> &graph, vector<bool> &visited,
                  vector<int> &toposort, int node) {
	visited[node] = true;
	for (auto i : graph[node]) {
		int a, b;
		tie(a, b) = i;
		if (visited[a]) { continue; }
		topo_sorting(graph, visited, toposort, a);
	}
	toposort.push_back(node);
}
 
int main() {
	ifstream fin("timeline.in");
 
	int n, m, c;
	fin >> n >> m >> c;
	vector<int> start(n + 1);
	for (int i = 1; i <= n; i++) { fin >> start[i]; }
 
	vector<vector<pair<int, int>>> graph(n + 1);
	for (int i = 0; i < c; i++) {
		int a, b, c;
		fin >> a >> b >> c;
		graph[a].push_back(make_pair(b, c));
	}
 
	/*
	 * Ordenamos topológicamente las sesiones de ordeño,
	 * empezando por la sesión de ordeño más temprana.
	 * Luego, de forma voraz, fijamos el tiempo de todos sus hijos
	 * para que sea al menos el tiempo propio + el peso de la arista.
	 */
	vector<bool> visited(n + 1);
	vector<int> toposort;
	for (int i = 1; i <= n; i++) {
		if (visited[i]) { continue; }
		topo_sorting(graph, visited, toposort, i);
	}
	for (int i = n - 1; i >= 0; i--) {
		for (auto j : graph[toposort[i]]) {
			int a, b;
			tie(a, b) = j;
			start[a] = max(start[a], start[toposort[i]] + b);
		}
	}
 
	ofstream fout("timeline.out");
	for (int i = 1; i <= n; i++) { fout << start[i] << "\n"; }
}


import java.io.*;
import java.util.*;
 
public class timeline {
	public static void main(String[] args) throws IOException {
		BufferedReader r = new BufferedReader(new FileReader("timeline.in"));
		PrintWriter pw = new PrintWriter("timeline.out");
		StringTokenizer st = new StringTokenizer(r.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
 
		// Leemos la fecha más temprana de cada sesión.
		st = new StringTokenizer(r.readLine());
		int[] time = new int[N];
		for (int i = 0; i < N; i++) { time[i] = Integer.parseInt(st.nextToken()); }
 
		ArrayList<edge>[] adj = new ArrayList[N];
		for (int i = 0; i < N; i++) { adj[i] = new ArrayList<>(); }
 
		// Leemos cada arista.
		int[] inDegree = new int[N];
		for (int i = 0; i < C; i++) {
			st = new StringTokenizer(r.readLine());
			int a = Integer.parseInt(st.nextToken()) - 1;
			int b = Integer.parseInt(st.nextToken()) - 1;
			int c = Integer.parseInt(st.nextToken());
			adj[a].add(new edge(b, c));
			inDegree[b]++;
		}
 
		// Agregamos a la cola todos los nodos "iniciales" sin aristas entrantes.
		Queue<Integer> q = new LinkedList<>();
		for (int i = 0; i < N; i++) {
			if (inDegree[i] == 0) { q.add(i); }
		}
 
		while (!q.isEmpty()) {
			int cur = q.poll();
			for (edge next : adj[cur]) {
				// Actualizamos el tiempo del siguiente nodo.
				int newTime = time[cur] + next.cost;
				time[next.node] = Integer.max(time[next.node], newTime);
 
				// Ya no hay aristas entrantes; agregamos este nodo a la cola.
				if (--inDegree[next.node] == 0) { q.add(next.node); }
			}
		}
 
		for (int i : time) { pw.println(i); }
		pw.close();
	}
 
	static class edge {
		public int node, cost;
 
		public edge(int node, int cost) {
			this.node = node;
			this.cost = cost;
		}
	}
}