Taco Route Challenge

You are given a number of cities and a cost matrix that represents the cost of traveling between any two cities. Starting at city 0, the goal is to find the minimum cost route that visits every other city exactly once and returns to city 0. This is a classic Traveling Salesman Problem (TSP) where the cost matrix is given and you must consider every permutation of cities (except the starting city) for a valid tour. The cost formula can be mathematically represented as:

\( \min_{\pi \in P(\{1,2,...,N-1\})}\left\{c(0, \pi_1) + \sum_{i=1}^{N-2} c(\pi_i, \pi_{i+1}) + c(\pi_{N-1}, 0) \right\}\)

Your task is to implement an algorithm that finds this minimum cost tour.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains an integer N, denoting the number of cities.
• The next N lines each contain N space-separated integers, representing the cost matrix. The j-th integer of the i-th line denotes the cost of going from city i to city j.

outputFormat

Output a single integer to standard output (stdout) which is the minimum cost to complete the tour starting and ending at city 0.

4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0

80