The Delivery Tour

A delivery van starts at the depot, city 0, must visit every other city exactly once, and then drive back to the depot. dist[i][j] is the driving time from city i to city j. It may differ from dist[j][i] because of one-way streets.

Write shortest_tour(dist) that returns the smallest total driving time of such a round trip. A tour is an order of the other cities: the van drives from the depot to the first city, then to the next, and so on, and from the last city back to the depot, adding up the time of each drive.

Examples

shortest_tour([[0, 2, 9], [1, 0, 6], [15, 7, 0]])                              # returns 17
shortest_tour([[0, 4, 1, 9], [3, 0, 6, 11], [4, 1, 0, 2], [6, 5, 4, 0]])     # returns 11
shortest_tour([[0]])                                                         # returns 0

In the first example the tour 0, 2, 1, 0 takes 9 + 7 + 1 = 17, while 0, 1, 2, 0 takes 2 + 6 + 15 = 23.

Constraints

• 1 <= n <= 13, where n = len(dist)
• 0 <= dist[i][j] <= 1000 and dist[i][i] == 0