Description

As you may already know, Jenny Cub is an avid camper and nature lover. This summer she was able to go all around the United States and visit a bunch of national and state parks such as Yellowstone National Park, and Theodore Roosevelt. She just loves walking around the parks and meeting new animal friends.

She has one complaint about the parks, however, and it involves the placement of the ranger stations in the parks. For some reason, the ranger stations are poorly layed out within the parks such that some campers would be placed far away from a station, which is bad should they need help (perhaps from a wandering bison).

To address this problem, Jenny Cub is asking you to figure out what is the best location to place a new ranger station to minimize the maximum distance form any campground to its nearest ranger station. Note that ranger stations are normally located near a campground, and thus share the same location.

Input

The input will be a series of park layouts, which consists of campgrounds and ranger stations. The first line of input in a set will be three numbers: S C P, where S denotes the number of ranger stations, while C denotes the number of campgrounds, and P is the number of paths between the campgrounds. There will never be more than 500 campgrounds. This is followed by the S campgrounds with a ranger station. After this, there will be a list of P path specifications in the form of Campground1 Campground2 Distance. Here is an sample input:

1 6 6
2
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 1 10

Output

For each park layout, you must figure out the lowest campground number at which a new ranger station should be built to minimize the maximum distance from any campground to its nearest ranger station. Here is an sample output:

5

Approach

Read in the campground and stations as a graph. Compute the All-Pairs-Shortest-Path for the graph using an algorithm like Floyd's. For each campground, add a station if one is not already present and compute the shortest distance from each site to the nearest station. Which ever new station produces the lowest total distance is the answer.

Input/Output

• Final input: problem023.input
• Final output: problem023.output

Source Code

• Peter Bui's source code: pbui.cc
• Jared Zenk's source code: jzenk.cpp