USACO Silver 2014 December - Piggy Back

Authors: Qi Wang, Kakulavaram Sanjana Reddy, David Zhou

Edit This Page

Official Analysis (C++)

Video Solution

By David Zhou

Video Solution Code

Explanation

We can BFS from the three points of Bessie, Elsie, and the barn. By doing so, we determine the distance from these three points to every other point. After, we can loop over all the cells and check the energy spent if it were the meeting location.

Implementation

Time Complexity: O(N+M)\mathcal{O}(N+M)

C++

#include <bits/stdc++.h>
using namespace std;


unordered_map<int, vector<int>> mp;
vector<vector<int>> dist;


// Function to find distance from node s to node ix
void distance(int s, int ix) {
	// Declare a queue to store the node and its distance from start node as a
	// pair

Java

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");

Python

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:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum