Minimum Cost Route Problem

You are given a complete graph where each node represents a delivery point, and node 0 is the depot. The graph is represented as an n × n distance matrix, where the element at the i^th row and j^th column, denoted by \(d_{ij}\), represents the distance from node \(i\) to node \(j\). Your task is to determine the minimum cost route that starts at the depot (node 0), visits each of the other nodes exactly once, and returns to the depot.

The cost of a route is the sum of the distances of consecutive nodes along the path. This is a typical Traveling Salesman Problem (TSP) solved here using a brute-force permutation approach, which is practical since \(2 \le n \le 10\).

inputFormat

The first line contains a single integer \(n\) (\(2\le n \le 10\)), which indicates the number of nodes (including the depot). Each of the following \(n\) lines contains \(n\) space-separated integers, forming the \(n \times n\) distance matrix. The j^th integer in the i^th line represents the distance from node \(i\) to node \(j\).

outputFormat

Output a single integer representing the minimum cost required to start at the depot (node 0), visit each other node exactly once, and return to the depot.

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

80