Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Traveling Trio
Description In the country of Byterland, cities are laid out along the shore of a beautiful river that flows from north to south. The northernmost city is labeled number 1, the city directly to its south is labeled number 2, etc. During the summer, ships are only allowed to travel south, or stay where they are, due to the huge number of tourists. There is always a route from each city Three people are planning to take journeys down the river, and they would like to coordinate their travel plans in order to minimize their total cost. Each person has their own individual starting and ending cities. The cost of traveling on any single ship route is always 1 dollar. If two or three people take the same route together as a group, the total ticket price is 1 dollar for the whole group. Please calculate the minimum total cost paid by the trio of travelers. Input On the first line of the input you will be given an integer The following The next line contains three integers E, _{i}i = 1, 2, 3).This is a multiple test cases problem. Test cases are followed by blank lines. Please process to the end of the file. Output For each test case, output a single line with an integer representing the minimum total cost paid by the trio of travellers. Sample Input 3 1 1 3 1 1 2 2 3 3 3 5 1 3 1 2 1 3 1 3 1 1 1 1 2 2 3 3 1 0 1 1 1 1 1 1 6 4 1 4 1 3 2 2 3 4 2 5 2 6 6 2 12 16 3 8 1 1 5 8 1 4 4 7 9 12 2 7 5 5 2 8 2 10 1 3 7 11 7 12 1 8 2 6 4 11 1 3 5 4 7 5 Sample Output 2 2 0 4 3 Hint Explanations of the sample test cases: For the first case: - 1st person: 1→2
- 2nd person: 1→2→3
- 3rd person: 2→3
The first and second person can share the ship going from city 1 to city 2. The second and third person can then share the ship going from city 2 to city 3. Only two ship routes are used, so the total cost is two dollars. For the second case: Exactly the same as the first test case. Duplicate routes and self-cycles can sometimes exist. Please remember that the 1→2 route is also a duplicate since the mandatory Source POJ Monthly--2006.12.31, Zhu, Zeyuan |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator