Frida is a writer for Cosmopolitan who writes restaurant reviews. She enjoys it a lot, but it seems that, throughout the years, she has reviewed all the restaurants on Earth. It’s now time to move one level up; she is going to review the food served by the airlines, so that the readers can make better decisions on which flights to take.
Her boss gave her a list of flight connections that she needs to review for the upcoming issue of Cosmopolitan. She knows that they serve the same food in both directions of every flight, so she only needs to take it once. She realized that she will need to take some additional flights, because she can not make all reviews using only flights in the list from her boss. Therefore she did some quick research and made a list of additional flights which she might take. She will not review the food on these flights; they will only be used so that she can make all the reviews.
Frida’s goal is to make all the reviews while spending the least money on flight tickets. Her office is in Stockholm, so she starts and ends her journey there. Each flight is both ways between two cities and has a fixed price in both directions. You can assume that it is possible to finish all the reviews using some of the additional flights.
For the purposes of this problem we ignore the price Frida has to pay for accommodation and we also ignore the departure and arrival times of flights by assuming that every flight is very often and reasonably short. We only focus on the total price of the flights.
입력 5 3 1 2 1000 2 3 1000 4 5 500 2 1 4 300 3 5 300 출력 3100 입력 6 5 1 2 1000 2 3 1000 1 3 1000 2 4 1000 5 6 500 2 2 5 300 4 6 300 출력 5100
출처:ncpc/2012/Problem F