#197HardDynamic Programming· Bitmask DP (Travelling Salesman)

Courier Round Trip Cost

A courier starts at the depot (location 0), must visit every other location exactly once, and then return to the depot. The travel cost from location `i` to location `j` is `cost[i][j]`; costs need not be symmetric (one-way streets, tolls), and `cost[i][i]` is 0. Return the minimum total cost of a tour that starts at location 0, visits each other location exactly once and ends back at location 0. If there is only one location, the tour costs 0.

Input format

`cost`: an `n x n` matrix of non-negative integers, where `cost[i][j]` is the price of travelling directly from location i to location j.

Output format

An integer: the minimum cost of a round trip that visits every location exactly once.

Examples

Input: cost = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]]

Output: 80

The best tour is 0 -> 1 -> 3 -> 2 -> 0 with cost 10 + 25 + 30 + 15 = 80.

Input: cost = [[0, 4], [7, 0]]

Output: 11

The courier must go 0 -> 1 (4) and come back 1 -> 0 (7): 11.

Input: cost = [[0]]

Output: 0

With one location there is nowhere to go.

Constraints

1 <= n <= 13
0 <= cost[i][j] <= 10^4 and cost[i][i] = 0
Every location can be reached directly from every other location.

Study first

#dynamic-programming
#bitmask
#travelling-salesman
#graph