Pro.ID22764 TitleCountry Roads Title链接http://10.20.2.8/oj/exercise/problem?problem_id=22764 AC0 Submit0 Ratio- 时间&空间限制描述It will be summer vocation soon. Bob want to go for a trip of his hometown. Assumes that there are N places Bob are interested in. And between any two places (for example, A and B) of them, there're exactly two roads, one from A to B, the other from B to A. Roads could be two types: R1 and R2. People take the bus in R1 roads and walk in R2 roads. Furthermore, Bob's hometown is small in area. Going from A to B, if there is a R2 road between them, it will take you T2 minutes. Or if there is a R1 road from A to B, only T1 minutes is enough. ( Of course, T1 < T2 ). You can not go by bus to travel from A, to B, to C, ... and finally return to A. In other words, there's not any cycles C1 -> C2-> ...-> Ck -> C1, that the roads from C1 to C2, from C2 to C3, ... from Ck to C1, are all R1 roads. The Information above is something about Bob's hometown. Now Bob is preparing for his summer trip. He wants to go from one place, visit all the interesting places, and return to the original place. Bob will stay at each place T minutes. Bob is busy; please help Bob to minimize the time he has to spend. Smart programmers, figure it out quickly please. Here is an example (as Figure 1 shows). There are 4 places in (a), and (b) is one of the optimal schedules ( A -> B -> C -> D -> A ). Solid lines are R1 roads, and the dot lines are R2 roads. According to (b), Bob has to spend T + T1 + T + T2 + T + T1 + T + T2 = 4T + 2T1 + 2T2 minutes.
( a ) ( b ) Figure 1 The Country Roads 输入The first line of the input is a positive integer C. C is the number of the test cases followed. Each test case contains two parts. First part are four integer N ( 1 < N < 100 ), T, T1, T2 ( 0 < T, T1, T2 < 100 ). The second part is a N×N matrix M. Bob have to spend M[i][j] minutes to go from place i to places j. As the problem statement, if i=j, M[i][j]=0; otherwise, M[i][j] is equal to T1 or T2 ( T1 < T2 ). There may be one or several spaces before or after the integers. All integers in the input file is smaller than 1000. 输出Description It will be summer vocation soon. Bob want to go for a trip of his hometown. Assumes that there are N places Bob are interested in. And between any two places (for example, A and B) of them, there're exactly two roads, one from A to B, the other from B to A. Roads could be two types: R1 and R2. People take the bus in R1 roads and walk in R2 roads. Furthermore, Bob's hometown is small in area. Going from A to B, if there is a R2 road between them, it will take you T2 minutes. Or if there is a R1 road from A to B, only T1 minutes is enough. ( Of course, T1 < T2 ). You can not go by bus to travel from A, to B, to C, ... and finally return to A. In other words, there's not any cycles C1 -> C2-> ...-> Ck -> C1, that the roads from C1 to C2, from C2 to C3, ... from Ck to C1, are all R1 roads. The Information above is something about Bob's hometown. Now Bob is preparing for his summer trip. He wants to go from one place, visit all the interesting places, and return to the original place. Bob will stay at each place T minutes. Bob is busy; please help Bob to minimize the time he has to spend. Smart programmers, figure it out quickly please. Here is an example (as Figure 1 shows). There are 4 places in (a), and (b) is one of the optimal schedules ( A -> B -> C -> D -> A ). Solid lines are R1 roads, and the dot lines are R2 roads. According to (b), Bob has to spend T + T1 + T + T2 + T + T1 + T + T2 = 4T + 2T1 + 2T2 minutes.
( a ) ( b ) Figure 1 The Country Roads Input The first line of the input is a positive integer C. C is the number of the test cases followed. Each test case contains two parts. First part are four integer N ( 1 < N < 100 ), T, T1, T2 ( 0 < T, T1, T2 < 100 ). The second part is a N×N matrix M. Bob have to spend M[i][j] minutes to go from place i to places j. As the problem statement, if i=j, M[i][j]=0; otherwise, M[i][j] is equal to T1 or T2 ( T1 < T2 ). There may be one or several spaces before or after the integers. All integers in the input file is smaller than 1000. Output The output of the program should consist of one line of output for each test case. The output of each test case only contains an integer S. S is the minimum time Bob has to spend. No any redundant spaces are needed. Sample Input 1 Sample Output 100 Source 样例输入1 样例输出100 作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2025-2-5 22:09 , Processed in 0.036810 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
