1373. Assignment Problem — Min Cost Bitmask DP

There are n workers and n jobs, and cost[i][j] is the price of giving job j to worker i. Assign every worker exactly one distinct job so that the total cost is as small as possible, and return that minimum total.

Input: A JSON object {"cost": [[...], ...]} describing an n x n matrix.

Output: Return the minimum total assignment cost.

Examples

Input: {"cost":[[9,2,7,8],[6,4,3,7],[5,8,1,8],[7,6,9,4]]}
Output: 13
Explanation: The optimal one-to-one assignment totals 13.

Input: {"cost":[[4,1],[2,3]]}
Output: 3
Explanation: Giving worker 0 the second job and worker 1 the first totals 3.

Constraints

• 1 <= n <= 15
• 0 <= cost[i][j] <= 10^6

Asked by