Travelling Salesman Problem 2 - MarisaOJ: Marisa Online Judge

Travelling Salesman Problem 2

Time limit: 2000 ms
Memory limit: 256 MB
There are $n$ cities. Going from city $i$ to city $j$ cost $A_{i, j}$ coins. Find the minimum cost route that visits each city exactly once and returns to the starting city. ### Input - The first line contains integers $n$. - Next $n$ lines, $i^{th}$ line contains $n$ integers $A_{i, j}$. ### Output - A single integers is the minimum cost. ### Constraints - $1 \le n \le 20$ - $0 \le A_{i, j} \le 1000$ ### Example Input: ``` 8 0 5 0 6 0 4 0 7 5 0 2 4 3 0 0 0 0 2 0 1 0 0 0 0 6 4 1 0 7 0 0 0 0 3 0 7 0 0 6 4 4 0 0 0 0 0 3 0 0 0 0 0 6 3 0 2 7 0 0 0 4 0 2 0 ``` Output: ``` 0 ```