Table of Contents

ExplanationImplementation

Explanation

Rather than treating the towns as nodes, instead treat the regions themselves as nodes with the walls as the edges still. We perform BFS from each node, logging the minimum distance from every region to every other region. Finally, we try all meeting regions and print out the one that minimizes the number of walls the members have to cross.

Implementation

Time Complexity: O(M2L)\mathcal{O}(M^2 L)

C++

#include <algorithm>
#include <iostream>
#include <map>
#include <vector>


using std::cout;
using std::endl;
using std::pair;
using std::vector;

Python

region_num = int(input())
town_num = int(input())
member_num = int(input())
members = [int(i) - 1 for i in input().split()]
assert member_num == len(members)


town_regions = [[] for _ in range(town_num)]
# contains the walls (represented as a pair of towns) for each region
regions = [[] for _ in range(region_num)]
for r in range(region_num):

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