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)

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!