Cheapest Visiting Order with Prerequisites
Problem statement
There are n points numbered 0 to n - 1. Moving directly from point i to point j costs cost[i][j]. The cost can be different in the two directions.
Each rules[k] = [a, b] means point a must be visited before point b.
Choose any starting point, at no cost. Then visit every point exactly once, moving directly from each point to the next one, and stop at the last point without coming back. The total cost is the sum of the costs of these moves.
Return the smallest total cost of a visiting order that follows every rule.
Function
minVisitCost(cost: int[][], rules: int[][]) → intExamples
Example 1
cost = [[0,4,1],[2,0,6],[3,5,0]]rules = []return = 3With no rules, every order is allowed. Starting at point 1, moving to point 0 costs 2, and then moving to point 2 costs 1, for a total of 3. No other order is cheaper. The answer is 3.
Example 2
cost = [[0,4,1],[2,0,6],[3,5,0]]rules = [[0,1],[1,2]]return = 10Point 0 must come before point 1, and point 1 before point 2, so the only allowed order is 0, 1, 2. It costs 4 + 6 = 10. The answer is 10.
Example 3
cost = [[0,7,2,9],[1,0,8,3],[6,2,0,4],[5,1,9,0]]rules = [[2,0]]return = 6Point 2 must be visited before point 0. The cheapest order overall, 3, 1, 0, 2, costs 1 + 1 + 2 = 4, but it visits point 0 before point 2, so it is not allowed. The best allowed order is 2, 3, 1, 0, which costs 4 + 1 + 1 = 6. The answer is 6.
Constraints
1 <= n == cost.length == cost[i].length <= 140 <= cost[i][j] <= 10^6andcost[i][i] == 00 <= rules.length <= n * (n - 1) / 2rules[k] = [a, b]with0 <= a, b < nanda != b, and no pair appears twice.- The rules never form a loop, so at least one order follows all of them.