Shortcut

Explicación

Un enfoque simple de fuerza bruta sería hallar el camino más corto para todos los nodos, y luego intentar agregar un atajo de $1$ a $i$ y hallar el camino más corto otra vez para todo $i$ .

Usando este enfoque, la respuesta es $\min(\texttt{dist}-\texttt{short}_i)$ para todo $i$ , donde $\texttt{dist}$ es el tiempo de viaje que toman todas las vacas sin un atajo y $\texttt{short}_i$ representa el tiempo de viaje que toman todas las vacas cuando hay un atajo de $1$ a $i$ . Aunque esto ciertamente dará TLE, sugiere una forma más rápida de calcular el tiempo ahorrado.

Llamemos $\texttt{occ}_i$ al número de vacas que pasan por el campo $i$ y $\texttt{trav}_i$ al costo para que una vaca vaya del campo $i$ a $1$ . Entonces la respuesta sería $\max(\texttt{occ}_i \cdot (\texttt{trav}_i - T))$ para todo $i$ . Esto funciona porque $\texttt{trav}_i - T$ calcula la disminución del tiempo de viaje para que una vaca llegue al campo $1$ . Al multiplicar este valor por $\texttt{occ}_i$ , calculamos la disminución de tiempo para todas las vacas que pasan por ese campo.

Podemos hallar los valores de $\texttt{trav}_i$ rápidamente con el algoritmo de Dijkstra. Para determinar $\texttt{occ}_i$ , almacenaremos los padres de los nodos mientras ejecutamos Dijkstra para poder retroceder y determinar los conteos de vacas que pasan. Podemos calcular $\texttt{occ}$ en $\mathcal{O}(N^2)$ dentro de los límites de tiempo porque $N \leq 10^4$ .

Implementación

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

C++Java


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	freopen("shortcut.in", "r", stdin);
	freopen("shortcut.out", "w", stdout);
 
	int n, m, t;
	cin >> n >> m >> t;
 
	vector<int> fields(n);
	for (int i = 0; i < n; i++) { cin >> fields[i]; }
 
	// adj[i] = {travel time, adjacent node}
	vector<vector<pair<int, int>>> adj(n);
	for (int i = 0; i < m; i++) {
		int u, v, c;
		cin >> u >> v >> c;
 
		adj[--u].push_back({c, --v});
		adj[v].push_back({c, u});
	}
 
	vector<int> cost(n, INT32_MAX);
 
	// prev stores parents for backtracking
	vector<int> prev(n, INT32_MAX);
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
 
	cost[0] = 0;
 
	// travel time, current node
	pq.push({0, 0});
	while (pq.size()) {
		pair<int, int> nxt = pq.top();
		pq.pop();
 
		int cur_cost = nxt.first;
		int cur_node = nxt.second;
 
		if (cur_cost != cost[cur_node]) { continue; }
 
		for (const pair<int, int> &u : adj[cur_node]) {
			// if this path is more optimal
			if (u.first + cur_cost < cost[u.second]) {
				cost[u.second] = u.first + cur_cost;
				pq.push({u.first + cur_cost, u.second});
				prev[u.second] = cur_node;
				/*
				 * keep paths lexicographically minimum by
				 * always choosing the lesser-indexed node
				 */
			} else if (u.first + cur_cost == cost[u.second] &&
			           cur_node < prev[u.second]) {
				prev[u.second] = cur_node;
			}
		}
	}
 
	vector<long long> occ(n);
	// backtrack
	for (int i = 0; i < n; i++) {
		int cur = i;
		while (cur != INT32_MAX) {
			occ[cur] += fields[i];
			cur = prev[cur];
		}
	}
 
	long long ans = 0;
	for (int i = 0; i < n; i++) { ans = max(ans, (long long)(occ[i] * (cost[i] - t))); }
	cout << ans << '\n';
}


import java.io.*;
import java.util.*;
 
public class Shortcut {
	static long[] farms;
	static List<Edge>[] adj;
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("shortcut");
 
		int N = io.nextInt();
		int M = io.nextInt();
		int T = io.nextInt();
		long[] dist = new long[N];
		farms = new long[N];
		adj = new List[N];
 
		for (int i = 0; i < N; i++) {
			farms[i] = io.nextInt();
			dist[i] = Integer.MAX_VALUE;
			adj[i] = new ArrayList<>();
		}
 
		for (int i = 0; i < M; i++) {
			int a = io.nextInt() - 1;
			int b = io.nextInt() - 1;
			int c = io.nextInt();
 
			adj[a].add(new Edge(a, b, c));
			adj[b].add(new Edge(b, a, c));
		}
 
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		pq.add(new Edge(0, 0, 0));
		List<Edge> fin = new ArrayList<>();
		while (!pq.isEmpty()) {
			Edge c = pq.poll();
 
			if (dist[c.t] <= c.e) { continue; }
			dist[c.t] = c.e;
			// Keep edges that form the shortest path tree
			fin.add(c);
 
			for (Edge e : adj[c.t]) {
				int nw = c.e + e.e;
 
				if (dist[e.t] <= nw) { continue; }
 
				pq.add(new Edge(c.t, e.t, nw));
			}
		}
		// Don't need the edge from 0 to 0
		fin.remove(0);
 
		for (int i = 0; i < N; i++) { adj[i].clear(); }
 
		// Turn tree into list
		for (int i = 0; i < fin.size(); i++) {
			Edge e = fin.get(i);
 
			adj[e.f].add(new Edge(e.f, e.t, 0));
		}
 
		dfs(0);
 
		long res = 0L;
		for (int i = 1; i < farms.length; i++) {
			res = Math.max(res, (dist[i] - T) * farms[i]);
		}
 
		io.println(res);
		io.close();
	}
 
	public static long dfs(int t) {
		for (Edge e : adj[t]) {
			// sum up cows travelling through farm t
			farms[t] += dfs(e.t);
		}
		return farms[t];
	}
 
	// BeginCodeSnip{Edge Class}
	private static class Edge implements Comparable<Edge> {
		int f, t, e;
		public Edge(int f, int t, int e) {
			this.t = t;
			this.e = e;
			this.f = f;
		}
 
		@Override
		public int compareTo(Edge o) {
			if (o.e == e) { return f - o.f; }
			return e - o.e;
		}
	}
	// EndCodeSnip
 
	// CodeSnip{Kattio}
}