Travelling Saleman Problem

Given a matrix B of size A x A where B[i][j] denotes the cost of moving from city i to city j.

Your task is to complete a tour from the city 0 (0 based index) to all other cities such that you visit each city at-most once and then at the end come back to city 0 in min cost.



Input Format:

    The First argument of input contains an integer A denoting number of nodes
    The Second argument of input contains a matrix B denoting cost of movement.

Output Format:

    Return the minimum cost of the tour.

Constraints:

1 <= A <= 10
0 <= B[i][j] <= 10000
B[i][i] = 0

For Example:

Input 1:
    A = 3 , B = [[0 500 100] [100 0 500] [500 100 0]]
Output 1:
    300
Explanation 1:
    The Tour is 0 -> 2 -> 1 -> 0
Input 2:
    A = 2 , B = [[0 5] [7 0]]
Output 2:
    12
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
Start solving Travelling Saleman Problem on Interview Code Editor
Sign Up
to access hints and editorial solutions for Travelling Saleman Problem

Discussion


Loading...
Click here to start solving coding interview questions