Please type your answers (include Excel solutions) and verify that all names from group members are included. Please be as descriptive as possible on the steps you took to obtain your solution. 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 as shown below (in $). Ams. Amsterdam Athens Berlin Brussels From Ath. Ber. Brus. 2166 577 175 2166 - 1806 2092 577 1806 653 175 2092 Copenhagen 622 2132 348 768 Dublin 712 2817 1273 732 Lisbon 1738 300 190 653 - 1889 2899 2345 Paris Rome 1203 2505 1656 London 339 2377 912 942 440 1616 Luxembourg 319 1905 598 797 914 1747 475 - 1254 293 987 Madrid 1462 2313 1836 1293 2046 1452 600 1259 1254 1033 1308 430 2100 78 262 1027 743 1482 331 293 1033 1297 1053 1184 1173 1527 1849 1907 1419 987 1308 - - Cope. Dub. Lis. Lon. Lux. Mad. Par. Rom. 622 712 1889 339 319 1462 430 1297 2132 2817 2899 2377 1905 2313 2100 1053 348 1273 2345 912 598 1836 878 1184 768 732 1738 300 190 1293 262 1173 1203 2505 942 797 2046 1027 1527 1656 440 914 1452 743 1849 1616 1747 1482 600 1907 475 1259 331 1419 1108 1108 What is the cheapest tour you can do to visit all 12 capital?