Flight Discount

Solución 1

Digamos que usamos el cupón de descuento en la arista entre las ciudades A y B.

Hay dos casos: podemos ir de $1\rightarrow A\rightarrow B\rightarrow N$ , o $1\rightarrow B\rightarrow A\rightarrow N$ . Necesitamos conocer la distancia entre $1$ y $A$ , y $N$ y $B$ .

Podemos usar Dijkstra para computar la distancia desde $1$ y $N$ hasta cada vértice. Luego nuestra respuesta es $\min\limits_{A\rightarrow B} \texttt{dist1}[A]+c(A,B)+\texttt{distN}[B]$ , donde $c(A,B)$ es el costo de viajar de la ciudad $A$ a la ciudad $B$ después de aplicar el cupón a ese vuelo, $\texttt{dist1}[A]$ es el costo de viajar de la ciudad $1$ a la ciudad $A$ y $\texttt{distN}[B]$ es el costo de viajar de la ciudad $B$ a la ciudad $N$ .

JavaC++


import java.io.*;
import java.util.*;
 
public class FlightDiscount {
	static class Flight {
		int to;
		long cost;
		Flight(int v, long wt) {
			this.to = v;
			this.cost = wt;
		}
	}
 
	// La clase que usaremos para representar el estado de Dijkstra
	static class Pos implements Comparable<Pos> {
		int pos;
		long cost;
		Pos(int val, long wsf) {
			this.pos = val;
			this.cost = wsf;
		}
 
		@Override
		public int compareTo(Pos o) {
			return (int)(this.cost - o.cost);
		}
	}
 
	// Hacer estas variables locales resulta en TLE en el último caso de prueba
	static List<List<Flight>> neighbors = new ArrayList<>();
	static List<List<Flight>> reverseNeighbors = new ArrayList<>();
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer initial = new StringTokenizer(br.readLine());
		int cityNum = Integer.parseInt(initial.nextToken());
		int flightNum = Integer.parseInt(initial.nextToken());
		for (int c = 0; c < cityNum; c++) {
			neighbors.add(new ArrayList<>());
			reverseNeighbors.add(new ArrayList<>());
		}
 
		for (int f = 0; f < flightNum; f++) {
			StringTokenizer flight = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(flight.nextToken()) - 1;
			int to = Integer.parseInt(flight.nextToken()) - 1;
			int cost = Integer.parseInt(flight.nextToken());
			neighbors.get(from).add(new Flight(to, cost));
			reverseNeighbors.get(to).add(new Flight(from, cost));
		}
 
		long[] dis1 = minDist(0, neighbors);
		long[] dis2 = minDist(cityNum - 1, reverseNeighbors);
		long minCost = Long.MAX_VALUE;
		for (int c = 0; c < cityNum; c++) {
			// Recorrer todos los vuelos y ver cuál es el costo mínimo
			for (Flight e : neighbors.get(c)) {
				minCost = Math.min(minCost, dis1[c] + dis2[e.to] + e.cost / 2);
			}
		}
		System.out.println(minCost);
	}
 
	public static long[] minDist(int start, ArrayList<ArrayList<Flight>> neighbors) {
		long[] minDist = new long[neighbors.size()];
		boolean[] visited = new boolean[neighbors.size()];
		PriorityQueue<Pos> frontier = new PriorityQueue<>();
		frontier.add(new Pos(start, 0));
		while (!frontier.isEmpty()) {
			Pos curr = frontier.remove();
			if (visited[curr.pos]) { continue; }
			visited[curr.pos] = true;
			minDist[curr.pos] = curr.cost;
			for (Flight e : neighbors.get(curr.pos)) {
				frontier.add(new Pos(e.to, curr.cost + e.cost));
			}
		}
		return minDist;
	}
}


#include <iostream>
#include <queue>
#include <vector>
 
using std::cout;
using std::endl;
using std::pair;
using std::vector;
 
/**
 * dado un punto de inicio, y una lista de adyacencia con costos,
 * esta función da un arreglo con las distancias mínimas
 * de todos los demás nodos al nodo de inicio
 * (el valor es INT64_MAX si es inalcanzable)
 */
vector<long long> min_costs(int from, const vector<vector<pair<int, int>>> &neighbors) {
	vector<long long> min_costs(neighbors.size(), INT64_MAX);
	min_costs[from] = 0;
	std::priority_queue<pair<long long, int>> frontier;
	frontier.push({0, from});
	while (!frontier.empty()) {
		pair<long long, int> curr_state = frontier.top();
		frontier.pop();
		int curr = curr_state.second;
		if (-curr_state.first != min_costs[curr]) { continue; }
 
		for (auto [n, nc] : neighbors[curr]) {
			long long new_cost = min_costs[curr] + nc;
			if (new_cost < min_costs[n]) {
				min_costs[n] = new_cost;
				frontier.push({-new_cost, n});
			}
		}
	}
	return min_costs;
}
 
int main() {
	int city_num;
	int flight_num;
	std::cin >> city_num >> flight_num;
	vector<vector<pair<int, int>>> neighbors(city_num);
	vector<vector<pair<int, int>>> reverse_neighbors(city_num);
	for (int f = 0; f < flight_num; f++) {
		int from;
		int to;
		int cost;
		std::cin >> from >> to >> cost;
		neighbors[--from].push_back({--to, cost});
		reverse_neighbors[to].push_back({from, cost});
	}
 
	vector<long long> start_costs = min_costs(0, neighbors);
	vector<long long> end_costs = min_costs(city_num - 1, reverse_neighbors);
	long long total_min = INT64_MAX;
	for (int c = 0; c < city_num; c++) {
		for (auto [n, nc] : neighbors[c]) {
			if (start_costs[c] == INT64_MAX || end_costs[n] == INT64_MAX) { continue; }
			total_min = std::min(total_min, start_costs[c] + (nc / 2) + end_costs[n]);
		}
	}
	cout << total_min << endl;
}

Solución 2

Como alternativa, podemos ejecutar Dijkstra y modificar ligeramente nuestro arreglo de distancias para llevar la cuenta de si el descuento se usó o no.

$\texttt{dist}[i][\texttt{false}]$ representará la distancia más corta del nodo de inicio al nodo $i$ , sin usar el descuento. $\texttt{dist}[i][\texttt{true}]$ representará la distancia más corta después de usar el descuento.

C++Java


#include <iostream>
#include <queue>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
int main() {
	int city_num;
	int flight_num;
	std::cin >> city_num >> flight_num;
	vector<vector<std::pair<int, int>>> neighbors(city_num);
	for (int f = 0; f < flight_num; f++) {
		int from;
		int to;
		int cost;
		std::cin >> from >> to >> cost;
		neighbors[--from].push_back({--to, cost});
	}
 
	vector<vector<long long>> min_cost(city_num, {INT64_MAX, INT64_MAX});
	min_cost[0] = {0, 0};
 
	struct Pos {
		int pos;         // la posición actual
		bool used;       // si ya usamos nuestro descuento
		long long cost;  // el costo asociado a este estado
	};
	auto cmp = [&](const Pos &a, const Pos &b) { return a.cost > b.cost; };
	std::priority_queue<Pos, vector<Pos>, decltype(cmp)> frontier(cmp);
	frontier.push({0, false, 0});
 
	while (!frontier.empty()) {
		Pos curr = frontier.top();
		frontier.pop();
		long long curr_cost = min_cost[curr.pos][curr.used];
		if (curr_cost != curr.cost) { continue; }
		if (curr.pos == city_num - 1) { break; }
		for (auto [n, nc] : neighbors[curr.pos]) {
			// si todavía no usamos el descuento, intentar usarlo ahora
			if (!curr.used) {
				long long new_cost = curr_cost + nc / 2;
				if (new_cost < min_cost[n][true]) {
					min_cost[n][true] = new_cost;
					frontier.push(Pos{n, true, new_cost});
				}
			}
			// pero siempre podemos intentar la ruta de costo normal
			if (curr_cost + nc < min_cost[n][curr.used]) {
				min_cost[n][curr.used] = curr_cost + nc;
				frontier.push(Pos{n, curr.used, curr_cost + nc});
			}
		}
	}
	cout << min_cost[city_num - 1][1];
}


import java.io.*;
import java.util.*;
 
public class FlightDiscount {
	static ArrayList<int[]>[] adj;
 
	// dist[i][0] = distancia más corta al nodo i sin usar el descuento
	// dist[i][1] = distancia más corta al nodo i después de usar el descuento
	static long[][] dist;
	static final long INF = (long)1e18;
 
	static class State implements Comparable<State> {
		int node;   // nodo actual
		int used;   // si el descuento se usó (0 = no, 1 = sí)
		long cost;  // costo total para alcanzar este estado
 
		State(int node, long cost, int used) {
			this.node = node;
			this.cost = cost;
			this.used = used;
		}
 
		@Override
		public int compareTo(State o) {
			return Long.compare(this.cost, o.cost);  // min-heap basado en el costo
		}
	}
 
	public static void main(String[] args) throws IOException {
		FastReader fr = new FastReader();
		PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
 
		int n = fr.nextInt();
		int m = fr.nextInt();
 
		adj = new ArrayList[n + 1];
		for (int i = 0; i <= n; i++) adj[i] = new ArrayList<>();
 
		for (int i = 0; i < m; i++) {
			int u = fr.nextInt();
			int v = fr.nextInt();
			int w = fr.nextInt();
			adj[u].add(new int[] {v, w});
		}
 
		dist = new long[n + 1][2];
		for (int i = 0; i <= n; i++) Arrays.fill(dist[i], INF);
 
		PriorityQueue<State> pq = new PriorityQueue<>();
		dist[1][0] = 0;  // Empezar en el nodo 1, descuento no usado
		pq.offer(new State(1, 0, 0));
 
		while (!pq.isEmpty()) {
			State s = pq.poll();
			int u = s.node;
			int used = s.used;
			long d = s.cost;
 
			// Saltar estado desactualizado
			if (d > dist[u][used]) continue;
 
			for (int[] edge : adj[u]) {
				int v = edge[0];
				int w = edge[1];
 
				// Caso 1: moverse sin usar el descuento
				if (dist[v][used] > d + w) {
					dist[v][used] = d + w;
					pq.offer(new State(v, dist[v][used], used));
				}
 
				// Caso 2: usar el descuento si todavía no se usó
				if (used == 0) {
					long newCost = d + (w / 2);
					if (dist[v][1] > newCost) {
						dist[v][1] = newCost;
						pq.offer(new State(v, newCost, 1));
					}
				}
			}
		}
		out.println(Math.min(dist[n][0], dist[n][1]));
		out.flush();
	}
 
	static class FastReader {
		BufferedReader br;
		StringTokenizer st;
 
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
 
		String next() throws IOException {
			while (st == null || !st.hasMoreTokens()) {
				String line = br.readLine();
				if (line == null) return null;
				st = new StringTokenizer(line);
			}
			return st.nextToken();
		}
 
		int nextInt() throws IOException { return Integer.parseInt(next()); }
		long nextLong() throws IOException { return Long.parseLong(next()); }
		double nextDouble() throws IOException { return Double.parseDouble(next()); }
		String nextLine() throws IOException { return br.readLine(); }
	}
}