1. You recently graduate and is planning a European trip. You decide to make one stop in each of 12 European capitals. You want to find a sequence of the cities that create the least total cost (you just graduated and do not have a salary still). By doing your research, you compute the plane costs between cities (in $). (a) What is the cheapest tour you can do to visit all 12 capital? (b) How much would that tour cost you? 1 A B Traveling (in the EU) C D E F G H J K L M N P a 2 3 Data To 4 Amsterdam Athens Berlin Brussels Copenhage Dublin Lisbon London Luxembourg Madrid Paris Rome 5 1 2 3 4 5 6 7 8 9 10 11 12 6 Amsterdam 1 0 2166 577 175 622 712 1889 339 319 1462 430 1297 7 Athens 2 2166 0 1806 2092 2132 2817 2899 2377 1905 2313 2100 1053 8 From Berlin 3 577 1806 0 653 348 1273 2345 912 598 1836 878 1184 9 Brussels 4 175 2092 653 0 768 732 1738 300 190 1293 262 1173 10 Copenhag 5 622 2132 348 768 0 1203 2505 942 797 2046 1027 1527 11 Dublin 6 712 2817 1273 732 1203 0 1656 440 914 1452 743 1849 12 Lisbon 7 1889 2899 2345 1738 2505 1656 0 1616 1747 600 1482 1907 13 London 8 339 2377 912 300 942 440 1616 0 475 1259 331 1419 14 Luxembou 9 319 1905 598 190 797 914 1747 475 0 1254 293 987 15 Madrid 10 1462 2313 1836 1293 2046 1452 600 1259 1254 0 1033 1308 16 Paris 11 430 2100 878 262 1027 743 1482 331 293 1033 0 1108 17 Rome 12 1297 1053 1184 1173 1527 1849 1907 1419 987 1308 1108 0 18 19 20 21