Minimal Energy to Visit All Checkpoints

You are given a complete graph with n checkpoints. The energy cost between every pair of checkpoints is provided in an n × n matrix \( C \), where \( C_{ij} \) represents the energy required to travel from checkpoint \( i \) to checkpoint \( j \). Your task is to determine the minimum total energy required to start at checkpoint 0, visit all other checkpoints exactly once, and return to checkpoint 0.

The problem can be mathematically formulated as a Traveling Salesman Problem (TSP):

Find the permutation \( \pi \) of \( \{1, 2, \dots, n-1\} \) which minimizes the total cost: \[ \min_{\pi} \left\{ C_{0,\pi(1)} + \sum_{i=1}^{n-2} C_{\pi(i),\pi(i+1)} + C_{\pi(n-1),0} \right\} \]

Note: The constraints guarantee that \( n \) is small (typically \( n \le 10 \)), so that a brute-force approach using permutations will work within the given limits.

inputFormat

The input is given via standard input. The first line contains a single integer \( n \) representing the number of checkpoints. This is followed by \( n \) lines, each containing \( n \) space-separated integers. The \( j^{th} \) integer in the \( i^{th} \) line represents the energy cost \( C_{ij} \) to travel from checkpoint \( i \) to checkpoint \( j \).

Example:

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

outputFormat

Output a single integer via standard output that represents the minimal total energy required to complete the round trip.

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

80