Taco Delivery: The Shortest Route Challenge

You are given a delivery problem where a taco delivery van needs to visit a number of locations and then return to the warehouse. The map is represented as a matrix of travel times between locations. The warehouse is designated as node 0, and there are N additional delivery locations labeled from 1 to N.

Your task is to determine the minimum total travel time required for the van to start at the warehouse, visit each of the N locations exactly once, and return to the warehouse. This is a classic traveling salesman problem (TSP).

Formally, given an integer N and a travel time matrix \(T\) of size \((N+1)\times(N+1)\), find the shortest possible route such that if the route is \(R = (0, i_1, i_2, \ldots, i_N, 0)\), then the total cost \[ \text{Cost}(R) = T_{0,i_1} + T_{i_1,i_2} + \cdots + T_{i_N,0} \] is minimized.

inputFormat

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

• The first line contains a single integer N (where N \(\geq 1\)), representing the number of delivery locations.
• The following N+1 lines each contain N+1 space-separated integers. The \(j\)-th integer on the \(i\)-th line represents the travel time from location \(i-1\) to location \(j-1\) (with the warehouse considered as location 0).

outputFormat

Output to stdout a single integer, which is the minimum total travel time for the van’s delivery route.

3
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0

80