Minimum Cycle Cost in Trucking Company

You are the operations manager for a trucking company that needs to connect its warehouses via a circular route. The task is to determine the minimum total mileage required to travel through every warehouse exactly once and return to the starting warehouse. This is a variant of the classic Traveling Salesman Problem (TSP).

Given an n × n cost matrix \(D\) where \(D[i][j]\) represents the cost (or mileage) to travel from warehouse \(i\) to warehouse \(j\), your goal is to find a permutation of the warehouses such that the total cost \[ \text{Cost} = D[p_1][p_2] + D[p_2][p_3] + \cdots + D[p_{n-1}][p_n] + D[p_n][p_1] \] is minimized. It is guaranteed that \(D[i][i] = 0\) for all \(i\), and the matrix may be either symmetrical or asymmetrical.

Help the company optimize its route and reduce operational costs!

inputFormat

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

• The first line contains an integer \(n\) (the number of warehouses).
• The following \(n\) lines each contain \(n\) space-separated integers, representing the cost matrix.

For example:

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

outputFormat

The output is written to standard output (stdout) and consists of a single integer: the minimum total mileage cost to complete the cycle as described.

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

80