1064 - Jogger
Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 10
Solved: 7
- Description
- Every morning, Joe the Jogger goes for a brisk run around his neighborhood. The houses in the neighbor-
hood (which are numbered from 1 to n) are connected together by a set of roads with the property that
between every two houses, there exists exactly one unique path. That is, the graph structure of the road
network is a tree of unknown topology, consisting of n leaf nodes (corresponding to each of the houses) and
up to n−1 (but possibly fewer) internal nodes denoting intersections where roads split or merge.
In this problem, your task is to help Joe plan a jogging route from one house in the neighborhood to
another house. Because Joe is a veteran jogger, he wants his route to take as long as possible. Given a
matrix of distances (in meters) between each pair of houses along the road graph, the number of seconds r
it takes Joe to run one meter, and the number of seconds t it takes for Joe to cross each intersection along
the route, determine the pair of houses for which the total travel time is as long as possible.
Figure 4: Diagram of neighborhood with n = 9. Houses correspond to numbered nodes, whereas internal
nodes of the tree (i.e., intersections) correspond to filled nodes. Note that multiple roads may meet at a
single intersection. Here, d3,9 = 9+1+7+6 = 23. If r = 1 and t = 5, then running from house 3 to house 9
takes Joe 1 × 23 + 3 × 5 = 38 seconds. In the neighborhood shown above, this is the longest possible route,
timewise, that Joe can take.
- Input
- The input test file will contain multiple cases. Each test case begins with a line containing three integers:
n (where 1 ≤ n ≤ 50), the total number of houses in the neighborhood, r (where 1 ≤ r ≤ 10), the number
of seconds per meter traveled, and t (where 1 ≤ t ≤ 100), the number of seconds needed to cross each in-
tersection. Then, the next n lines each contain n values indicating the distances dij (where 1 ≤ dij ≤ 1000)
between each pair of houses. The distances are specified in row-major order; i.e., the jth entry of the ith
line is dij .
You are guaranteed that dii = 0 for each i and that dij = dji for i = j. Furthermore, you may as-
sume that the distance matrix corresponds to path lengths along some valid tree, no house coincides with
any internal node of the tree, each internal node of the tree has degree ≥ 3, and all edges in the tree have
positive length. Input is terminated by a single line containing the number 0; do not process this line.
- Output
- For each test case, you must print a single line of output containing the longest total travel time possible.
- sample input
-
9 1 5 0 8 22 16 16 13 24 14 11 8 0 20 14 14 11 22 12 9 22 20 0 12 12 11 22 12 23 16 14 12 0 4 5 16 6 17 16 14 12 4 0 5 16 6 17 13 11 11 5 5 0 13 3 14 24 22 22 16 16 13 0 14 25 14 12 12 6 6 3 14 0 15 11 9 23 17 17 14 25 15 0 0
- sample output
-
38
- hint
- source
- Stanford Local 2007