Skip to Content
CTRL K

Piggy Back

Análisis oficial (C++) 

Solución en video

Por David Zhou

Video de YouTube (7IHPKEPe1w0)

Código de la solución en video
#include <climits>
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
vector<vector<int>> adj;
 
void bfs(int start, vector<int> &dist) {
	dist[start] = 0;
	queue<int> q;
	q.push(start);
	while (!q.empty()) {
		int curr = q.front();
		q.pop();
		for (int next : adj[curr]) {
			if (dist[next] == -1) {
				dist[next] = dist[curr] + 1;
				q.push(next);
			}
		}
	}
}
 
int main() {
	// E/S antigua
	freopen("piggyback.in", "r", stdin);
	freopen("piggyback.out", "w", stdout);
	int B, E, P, n, m;
	cin >> B >> E >> P >> n >> m;
	adj.resize(n);
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		adj[--a].push_back(--b);
		adj[b].push_back(a);
	}
 
	vector<int> bessie_dist(n, -1), elsie_dist(n, -1), barn_dist(n, -1);
	// BFS desde cada punto de partida
	bfs(0, bessie_dist);
	bfs(1, elsie_dist);
	bfs(n - 1, barn_dist);
 
	int res = INT_MAX;
	for (int i = 0; i < n; i++) {
		int b_dist = bessie_dist[i] * B, e_dist = elsie_dist[i] * E;
		int barn =
		    barn_dist[i] * min(B + E, P);  // P puede no ser más óptimo que B + E
		res = min(res, b_dist + e_dist + barn);
	}
 
	cout << res << endl;
}
import java.io.*;
import java.util.*;
 
public class Piggyback {
 
	static List<List<Integer>> adj;
 
	public static void bfs(int start, int[] dist) {
		Arrays.fill(dist, -1);
		dist[start] = 0;
		Queue<Integer> q = new LinkedList<>();
		q.add(start);
		while (!q.isEmpty()) {
			int curr = q.poll();
			for (int next : adj.get(curr)) {
				if (dist[next] == -1) {
					dist[next] = dist[curr] + 1;
					q.add(next);
				}
			}
		}
	}
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("piggyback.in"));
		PrintWriter pw =
		    new PrintWriter(new BufferedWriter(new FileWriter("piggyback.out")));
 
		StringTokenizer st = new StringTokenizer(br.readLine());
		int B = Integer.parseInt(st.nextToken());
		int E = Integer.parseInt(st.nextToken());
		int P = Integer.parseInt(st.nextToken());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
 
		adj = new ArrayList<>();
		for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
 
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken()) - 1;
			int b = Integer.parseInt(st.nextToken()) - 1;
			adj.get(a).add(b);
			adj.get(b).add(a);
		}
 
		int[] bessieDist = new int[n];
		int[] elsieDist = new int[n];
		int[] barnDist = new int[n];
		// BFS desde cada punto de partida
		bfs(0, bessieDist);
		bfs(1, elsieDist);
		bfs(n - 1, barnDist);
 
		int res = Integer.MAX_VALUE;
		for (int i = 0; i < n; i++) {
			int bCost = bessieDist[i] * B;
			int eCost = elsieDist[i] * E;
			int pCost = barnDist[i] *
			            Math.min(B + E, P);  // P puede no ser más óptimo que B + E
			res = Math.min(res, bCost + eCost + pCost);
		}
 
		pw.println(res);
		pw.close();
		br.close();
	}
}
from collections import deque
 
 
def bfs(start, dist, adj):
	dist[start] = 0
	q = deque([start])
	while q:
		curr = q.popleft()
		for neighbor in adj[curr]:
			if dist[neighbor] == -1:
				dist[neighbor] = dist[curr] + 1
				q.append(neighbor)
 
 
def main():
	with open("piggyback.in", "r") as fin:
		B, E, P, n, m = map(int, fin.readline().split())
		adj = [[] for _ in range(n)]
 
		for _ in range(m):
			a, b = map(int, fin.readline().split())
			a -= 1
			b -= 1
			adj[a].append(b)
			adj[b].append(a)
 
	bessie_dist = [-1] * n
	elsie_dist = [-1] * n
	barn_dist = [-1] * n
 
	# BFS desde cada punto de partida
	bfs(0, bessie_dist, adj)
	bfs(1, elsie_dist, adj)
	bfs(n - 1, barn_dist, adj)
 
	res = float("inf")
	for i in range(n):
		b_cost = bessie_dist[i] * B
		e_cost = elsie_dist[i] * E
		p_cost = barn_dist[i] * min(B + E, P)  # P puede no ser más óptimo que B + E
		res = min(res, b_cost + e_cost + p_cost)
 
	with open("piggyback.out", "w") as fout:
		fout.write(f"{res}\n")
 
 
if __name__ == "__main__":
	main()

Explicación

Podemos hacer BFS desde los tres puntos de Bessie, Elsie y el granero. Al hacerlo, determinamos la distancia desde estos tres puntos hasta todos los demás. Después, recorremos todas las celdas y comprobamos la energía gastada si esa fuera la ubicación de encuentro.

Implementación

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

#include <bits/stdc++.h>
using namespace std;
 
unordered_map<int, vector<int>> mp;
vector<vector<int>> dist;
 
// Función para encontrar la distancia desde el nodo s hasta el nodo ix
void distance(int s, int ix) {
	// Declarar una cola para almacenar el nodo y su distancia desde el nodo de
	// inicio como un par
	queue<pair<int, int>> q;
	q.push({s, 0});
	dist[ix][s] = 0;
	while (!q.empty()) {
		pair<int, int> p = q.front();
		q.pop();
		for (int n : mp[p.first]) {
			if (dist[ix][n] != -1) { continue; }
			dist[ix][n] = p.second + 1;
			q.push({n, dist[ix][n]});
		}
	}
}
 
int main() {
	int B, E, P, N, M;
	cin >> B >> E >> P >> N >> M;
	dist.assign(4, vector<int>(N + 1, -1));
	for (int i = 0; i < M; i++) {
		int u, v;
		cin >> u >> v;
		mp[--u].push_back(--v);
		mp[v].push_back(u);
	}
 
	distance(0, 0);      // encontrar la distancia de cada nodo desde el nodo 0
	distance(1, 1);      // encontrar la distancia de cada nodo desde el nodo 1
	distance(N - 1, 2);  // encontrar la distancia de cada nodo desde el nodo N - 1
 
	int min_energy = INT32_MAX;
	for (int i = 0; i < N; i++) {
		int energy = dist[0][i] * B + dist[1][i] * E + dist[2][i] * min(B + E, P);
		min_energy = min(min_energy, energy);
	}
	cout << min_energy << endl;
}
import java.io.*;
import java.util.*;
 
public class Piggyback {
	static int B, E, P, N, M, A = Integer.MAX_VALUE;
	static List<Integer>[] adj;
	static int[][] dist;
	public static void main(String[] args) throws Exception {
		Kattio io = new Kattio("piggyback");
 
		B = io.nextInt();
		E = io.nextInt();
		P = io.nextInt();
		N = io.nextInt();
		M = io.nextInt();
 
		adj = new List[N];
		dist = new int[3][N];
 
		for (int i = 0; i < 3; i++) { Arrays.fill(dist[i], -1); }
 
		for (int i = 0; i < N; i++) { adj[i] = new ArrayList<>(); }
 
		for (int i = 0; i < M; i++) {
			int a = io.nextInt() - 1;
			int b = io.nextInt() - 1;
 
			adj[a].add(b);
			adj[b].add(a);
		}
 
		bfs(0, 0);
		bfs(1, 1);
		bfs(N - 1, 2);
 
		for (int i = 0; i < N; i++) {
			A = Math.min(A, dist[0][i] * B + dist[1][i] * E +
			                    dist[2][i] * Math.min(B + E, P));
		}
 
		io.println(A);
		io.close();
	}
 
	private static void bfs(int s, int ix) {
		Queue<Path> q = new LinkedList<>();
		q.add(new Path(s, 0));
		dist[ix][s] = 0;
 
		while (!q.isEmpty()) {
			Path curr = q.poll();
 
			for (Integer n : adj[curr.i]) {
				if (dist[ix][n] != -1) continue;
				dist[ix][n] = curr.d + 1;
 
				q.add(new Path(n, dist[ix][n]));
			}
		}
	}
 
	private static class Path {
		int i, d;
		public Path(int a, int b) {
			i = a;
			d = b;
		}
	}
 
	// CodeSnip{Kattio}
}
from collections import deque
 
 
def bfs(start, dist, adj):
	dist[start] = 0
	q = deque([start])
	while q:
		curr = q.popleft()
		for neighbor in adj[curr]:
			if dist[neighbor] == -1:
				dist[neighbor] = dist[curr] + 1
				q.append(neighbor)
 
 
def main():
	with open("piggyback.in", "r") as fin:
		B, E, P, n, m = map(int, fin.readline().split())
		adj = [[] for _ in range(n)]
 
		for _ in range(m):
			a, b = map(int, fin.readline().split())
			a -= 1
			b -= 1
			adj[a].append(b)
			adj[b].append(a)
 
	bessie_dist = [-1] * n
	elsie_dist = [-1] * n
	barn_dist = [-1] * n
 
	# BFS desde cada punto de partida
	bfs(0, bessie_dist, adj)
	bfs(1, elsie_dist, adj)
	bfs(n - 1, barn_dist, adj)
 
	res = float("inf")
	for i in range(n):
		b_cost = bessie_dist[i] * B
		e_cost = elsie_dist[i] * E
		p_cost = barn_dist[i] * min(B + E, P)  # P puede no ser más óptimo que B + E
		res = min(res, b_cost + e_cost + p_cost)
 
	print(res, file=open("piggyback.out", "w"))
 
 
if __name__ == "__main__":
	main()
Fundamentos