#include <iostream>
#include <cstdio>
using namespace std;
int distance[31][31] =
{{6371, 1078, 119, 263, 398, 401, 634, 866, 1061, 367, 905, 902, 1135, 1255, 1568, 1729, 626, 1052, 1343, 1893, 2286, 2050, 909, 879, 1178, 1321, 2399, 1511, 1732, 2085, 2558},
{1078, 6371, 963, 989, 1096, 1381, 1189, 1451, 1679, 735, 269, 399, 160, 601, 606, 686, 824, 685, 881, 1210, 1666, 1599, 1218, 1597, 1717, 1908, 3265, 1655, 1522, 1956, 2909},
{119, 963, 6371, 262, 426, 504, 605, 860 ,1068, 271, 798, 806, 1025, 1169, 1465, 1620, 582, 981, 1277, 1819, 2223, 2001, 913, 947, 1228, 1381, 2502, 1518, 1702, 2071, 2604},
{263, 989, 262, 6371, 171, 394, 867, 1117, 1318, 266, 769, 730, 1010, 1049, 1403, 1590, 376, 823, 1104, 1662, 2042, 1794, 654, 720, 977, 1138, 2336, 1258, 1469, 1823, 2347},
{398, 1096, 426, 171, 6371, 341, 1025, 1264, 1457, 412, 854, 790, 1095, 1065, 1452, 1655, 359, 816, 1074, 1637, 1991, 1720, 516, 555, 807, 968, 2192, 1114, 1368, 1700, 2179},
{401, 1381, 504, 394, 341, 6371, 987, 1171, 1325, 650, 1161, 1114, 1403, 1405, 1783, 1978, 700, 1157, 1411, 1973, 2315, 2029, 770, 535, 870, 981, 1999, 1320, 1649, 1942, 2237},
{634, 1189, 605, 867, 1025, 987, 6371, 281, 512, 790, 1155, 1227, 1314, 1607, 1785, 1870, 1158, 1484, 1782, 2280, 2714, 2535, 1518, 1504, 1812, 1950, 2909, 2123, 2278, 2662, 3192},
{866, 1451, 860, 1117, 1264, 1171, 281, 6371, 232, 1065, 1432, 1507, 1582, 1887, 2053, 2124, 1428, 1765, 2063, 2561, 2995, 2815, 1770, 1703, 2026, 2151, 2998, 2375, 2551, 2929, 3402},
{1061, 1679, 1068, 1318, 1457, 1325, 512, 232, 6371, 1287, 1664, 1738, 1813, 2118, 2282, 2349, 1645, 1993, 2291, 2792, 3225, 3041, 1970, 1860, 2193, 2306, 3057, 2572, 2768, 3139, 3561},
{367, 735, 271, 266, 412, 650, 790, 1065, 1287, 6371, 540, 537, 775, 899, 1201, 1367, 374, 720, 1019, 1553, 1964, 1757, 780, 964, 1185, 1359, 2599, 1370, 1488, 1878, 2528},
{905, 269, 798, 769, 854, 1161, 1155, 1432, 1664, 540, 6371, 141, 242, 467, 668, 827, 560, 456, 704, 1136, 1581, 1459, 949, 1336, 1448, 1640, 3004, 1404, 1320, 1750, 2653},
{902, 399, 806, 730, 790, 1114, 1227, 1507, 1738, 537, 141, 6371, 328, 380, 674, 866, 463, 319, 584, 1054, 1490, 1344, 824, 1237, 1328, 1520, 2902, 1264, 1185, 1614, 2514},
{1135, 160, 1025, 1010, 1095, 1403, 1314, 1582, 1813, 775, 242, 328, 6371, 447, 472, 596, 788, 566, 733, 1051, 1506, 1441, 1147, 1564, 1653, 1845, 3229, 1543, 1378, 1812, 2799},
{1255, 601, 1169, 1049, 1065, 1405, 1607, 1887, 2118, 899, 467, 380, 447, 6371, 441, 687, 706, 270, 291, 674, 1115, 1004, 908, 1404, 1401, 1589, 3020, 1166, 938, 1370, 2414},
{1568, 606, 1465, 1403, 1452, 1783, 1785, 2053, 2282, 1201, 668, 674, 472, 441, 6371, 252, 1103, 705, 666, 697, 1137, 1171, 1348, 1836, 1842, 2030, 3461, 1573, 1256, 1666, 2800},
{1729, 686, 1620, 1590, 1655, 1978, 1870, 2124, 2349, 1367, 827, 866, 596, 687, 252, 6371, 1317, 945, 916, 869, 1276, 1366, 1589, 2067, 2087, 2276, 3704, 1824, 1493, 1892, 3046},
{626, 824, 582, 376, 359, 700, 1158, 1428, 1645, 374, 560, 463, 788, 706, 1103, 1317, 6371, 459, 730, 1291, 1666, 1424, 437, 777, 906, 1094, 2444, 1003, 1123, 1505, 2194},
{1052, 685, 981, 823, 816, 1157, 1484, 1765, 1993, 720, 456, 319, 566, 270, 705, 945, 459, 6371, 299, 842, 1243, 1054, 644, 1134, 1144, 1334, 2758, 976, 867, 1295, 2233},
{1343, 881, 1277, 1104, 1074, 1411, 1782, 2063, 2291, 1019, 704, 584, 733, 291, 666, 916, 730, 299, 6371, 563, 946, 762, 778, 1298, 1229, 1408, 2848, 908, 647, 1080, 2141},
{1893, 1210, 1819, 1662, 1637, 1973, 2280, 2561, 2792, 1553, 1136, 1054, 1051, 674, 697, 869, 1291, 842, 563, 6371, 455, 505, 1306, 1825, 1698, 1858, 3278, 1235, 761, 1087, 2324},
{2286, 1666, 2223, 2042, 1991, 2315, 2714, 2995, 3225, 1964, 1581, 1490, 1506, 1115, 1137, 1276, 1666, 1243, 946, 455, 6371, 373, 1587, 2082, 1889, 2021, 3378, 1339, 816, 959, 2220},
{2050, 1599, 2001, 1794, 1720, 2029, 2535, 2815, 3041, 1757, 1459, 1344, 1441, 1004, 1171, 1366, 1424, 1054, 762, 505, 373, 6371, 1274, 1748, 1533, 1657, 3005, 971, 449, 619, 1883},
{909, 1218, 913, 654, 516, 770, 1518, 1770, 1970, 780, 949, 824, 1147, 908, 1348, 1589, 437, 644, 778, 1306, 1587, 1274, 6371, 521, 507, 699, 2114, 604, 880, 1187, 1758},
{879, 1597, 947, 720, 555, 535, 1504, 1703, 1860, 964, 1336, 1237, 1564, 1404, 1836, 2067, 777, 1134, 1298, 1825, 2082, 1748, 521, 6371, 346, 448, 1668, 885, 1318, 1526, 1701},
{1178, 1717, 1228, 977, 807, 870, 1812, 2026, 2193, 1185, 1448, 1328, 1653, 1401, 1842, 2087, 906, 1144, 1229, 1698, 1889, 1533, 507, 346, 6371, 192, 1622, 596, 1087, 1226, 1380},
{1321, 1908, 1381, 1138, 968, 981, 1950, 2151, 2306, 1359, 1640, 1520, 1845, 1589, 2030, 2276, 1094, 1334, 1408, 1858, 2021, 1657, 699, 448, 192, 6371, 1440, 691, 1208, 1288, 1255},
{2399, 3265, 2502, 2336, 2192, 1999, 2909, 2998, 3057, 2599, 3004, 2902, 3229, 3020, 3461, 3704, 2444, 2758, 2848, 278, 3378, 3005, 2114, 1668, 1622, 1440, 6371, 2053, 2570, 2494, 1592},
{1511, 1655, 1518, 1258, 1114, 1320, 2123, 2375, 2572, 1370, 1404, 1264, 1543, 1166, 1573, 1824, 1003, 976, 908, 1235, 1339, 971, 604, 885, 596, 691, 2053, 6371, 523, 641, 1257},
{1732, 1522, 1702, 1469, 1368, 1649, 2278, 2551, 2768, 1488, 1320, 1185, 1378, 938, 1256, 1493, 1123, 867, 647, 761, 816, 449, 880, 1318, 1087, 1208, 2570, 523, 6371, 434, 1574},
{2085, 1956, 2071, 1823, 1700, 1942, 2662, 2929, 3139, 1878, 1750, 1614, 1812, 1370, 1666, 1892, 1505, 1295, 1080, 1087, 959, 619, 1187, 1526, 1226, 1288, 2494, 641, 434, 6371, 1266},
{2558, 2909, 2604, 2347, 2179, 2237, 3192, 3402, 3561, 2528, 2653, 2514, 2799, 2414, 2800, 3046, 2194, 2233, 2141, 2324, 2220, 1883, 1758, 1701, 1380, 1255, 1592, 1257, 1574, 1266, 6371}
};
//6371为自己到自己
//distance[i][j]为从i到j的距离
int city_pass_by[31]={32,32,32,32,32,32,32,32,32,32,32,
32,32,32,32,32,32,32,32,32,32,
32,32,32,32,32,32,32,32,32,32};
//32表示未经过,其他均表示未经过
bool pass_or_not(int a)
{
for (int i = 0; i < 31; i++)
if (city_pass_by[i]==a) return 1;
return 0;
}
void nearest_city(int city)//找最近的城市
{
int temp=6371;
for(int i = 0;i<31;i++ )
{
if (pass_or_not(i) == 0 && ::distance[i][city] < temp) {
temp = ::distance[i][city];
city_pass_by[city + 1] = i;//标记city被访问,被访问过的城市标为i
}
}
for(int i = 0;i<31;i++)
{
if(city_pass_by[i] == 32)
nearest_city(city_pass_by[city+1]);
}
}
void TSP()
{
long long int sum = 0;
int start;//表示开始的城市
cin>>start;
city_pass_by[0] = start;
nearest_city(city_pass_by[0]);
for(int i = 0;i<31;i++ )
{
if(i == 30) {
cout << city_pass_by[i] << "->"
<< city_pass_by[0] << " 距离为:" << " " << ::distance[city_pass_by[30]][city_pass_by[0]];
sum += ::distance[city_pass_by[30]][city_pass_by[0]];
cout << endl<<"总距离" << sum;
break;
}
printf("%d->%d 距离为: %d\n",city_pass_by[i],city_pass_by[i+1],::distance[city_pass_by[i]][city_pass_by[i+1]]);
sum += ::distance[city_pass_by[i]][city_pass_by[i+1]];
}
}
int main()
{
TSP();
return 0;
}
从部分城市为起点时（比如说5），56行报错SIGSEGV (Segmentation fault)，但是大部分输入可以正常输出，不知道问题在哪