Question

Problem Description Sejal was on a month-long vacation to Europe and has a return trip to India from Lisbon, a city in south west part of Europe. However, a day before the return flight she realizes that she lost her engagement ring. After much contemplation, she decides to go to all the cities she visited to find her ring. She maps all the cities she visited on a graph with Lisbon being at point (0,0). She then makes a route plan to visit all the cities and return to Lisbon by taking the shortest possible distance. She does not remember having her ring even in the first city she visited so there are high chances that she may have lost her ring in the initial part of her trip also. In case there are more than one routes which have the shortest possible distance, she picks that route in which the first city she visited, comes first. For example, if she visited cities 2,5,7,1,8,3 in that order and routes 0,1,8,3,2,5,7,0 and 0,8,3,1,5,2,7,0 (0 being Lisbon) have the same shortest possible distance then she will choose route 0,1,8,3,2,5,7,0 because she visited city 1 before city 8. Her travel guide, Harry also offers to help Sejal. Sejal asks him to travel separately on the same route, but in reverse direction such that each city is visited only once. They plan to travel 20 Kms in each city on taxi to search the ring. Inter-city travel is done on trains only. A secret service officer knows the coordinates of the city that Sejal visited during her the trip in that order. He also knows the city in which the ring is lost but will inform Sejal or Harry only when one of the two is in that city. He knows the path that Sejal has drawn to visit all the cities and return to Lisbon. With Sejal and Harry following that path and either one of them reaching the city where the ring is lost, the secret service officer will inform the person in that city, that the ring will be 10 km away from their current location. They will travel back 10 km in the same city, to catch the train back to Lisbon. Calculate the total distance traveled by Sejal in her search and her return to Lisbon from that city. If the ring is found by Sejal, she goes back to Lisbon from that city. If the ring is found by Harry, he informs Sejal on call at that point. If Sejal is in a city (searching in taxi) she returns to Lisbon via train from that city (without searching any further in that city). If Sejal is on train, she will need to complete the journey and then return from that other city. If the call comes at the exact point she is taking a train, she can return from that city itself. Each unit in the graph is equal to 1 Km. Assume the speed of all trains and taxis is same. Do not consider the decimal values while calculating the distance between two cities, ie. distance will be the floor of the calculated distance. Constraints Floor of the value is to be used while calculating distance between cities Each city is connected to every other city via trains Total number of cities <10 Input First Line will provide the coordinates (x|y) of cities separated by semicolon (;) Second Line will provide the number of city where the ring is found Output One integer representing the number total distance traveled by Sejal Time Limit 1 Examples Example 1 Input 0|90;90|90;90|0 2 Output 347 Explanation Since routes 1,2,3 and 3,2,1 will give the shortest distance, she will select route 1,2,3 as she visited city 1 before city 3. However, Harry will follow the opposite path - 3,2,1. They both will be in city 2 when they will find it. Total distance Sejal covers will be Lisbon to city 1 + 20Kms, City 1 to City 2 + 10 km +10 km and then City 2 to Lisbon. i.e. 90 + 20 + 90 + 20 +127 = 347 km Example 2 Input 10|70;30|30;80|20;120|75;90|120 3 Output 334 Explanation Sejal will choose the route 1, 5, 4, 3, 2 with minimum distance of 378 km. However, Harry will follow the opposite path - and will find the ring in City 3. The moment Harry finds the ring, Sejal will be travelling from City 1 to City 5. So she will complete the journey till City 5 and return from there to Lisbon. So the total distance covered by Sejal will be 70+20+94+150 = 334 km What is Program solution?

Answer 1

Answer:

I am sorry but I am not able to understand what exactly is this....