Description
Write a Java program that solves the symmetric Traveling Salesman Problem by
implementing the dynamic programming algorithm discussed in class. You are
given n cities, labelled 0, 1, 2, …, n-1. Assume that you start from city 0 and n
is a positive integer greater than or equal to 5.
Input
The input consists of a sequence of 20 test cases. Each test case consists of n
+ 1 lines, where n is the number of cities. In the first line, n is given. In the
next n lines, the inter-city distances are given as an nxn matrix. If an element
of matrix has ‘-1’, there is no edge connected. Assume each of other elements
is non-negative integer no greater than 1,000.
Output
There should be one line of output for each test case in the input file. For each
test case, print out a single integer, indicating the length of an optimal route.
Sample Input
20 // number of test cases
10 // n =10 test case #1
-1 7 -1 6 -1 -1 7 10 -1 -1 // 10×10 matrix is given
7 -1 8 5 -1 -1 13 -1 -1 -1
-1 8 -1 7 6 5 -1 -1 10 -1
6 5 7 -1 4 -1 8 11 -1 -1
-1 -1 6 4 -1 5 -1 10 7 -1
-1 -1 5 -1 5 -1 -1 -1 6 4
2
Sample Output
Figure for Sample Input/Output
7 13 -1 8 -1 -1 -1 4 -1 -1
10 -1 -1 11 10 -1 4 -1 12 -1
-1 -1 10 -1 7 6 -1 12 -1 7
-1 -1 -1 -1 -1 4 -1 -1 7 -1
5 // // n =5 test case #2
…
61 // optimal length of test case #1
…
