Jogger
문제 정보
-
- 문제 ID
- 시간 제한
- 메모리 제한
- 제출 횟수
- 정답 횟수 (비율)
-
- 출처
- 분류
문제
Every morning, Joe the Jogger goes for a brisk run around his neighborhood. The houses in the neighborhood (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 (see Figure 4).
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.
입력
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 intersection. 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 6= 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.
출력
For each test case, you must print a single line of output containing the longest total travel time possible.
예제 입력
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
예제 출력
38
노트