A checkout flow has n steps numbered 0 to n - 1. Each edges[i] = [from, to, cost] is a possible move from step from to step to that adds cost to the order total. Some moves apply a refund, so cost can be negative.
Write cheapestCosts(n, edges, start) that returns an array where entry i is the cheapest total to get from start to step i, or null if step i can't be reached. If a loop with a negative total can be reached from start, there is no cheapest total, so return [] instead.
Input: n = 4, edges = [[0,1,4],[0,2,5],[2,1,-3],[1,3,2]], start = 0 Output: [0,2,5,4]
Step 1 is cheapest through the refund: 5 - 3 = 2. Then step 3 costs 2 + 2 = 4.
Input: n = 3, edges = [[0,1,1],[1,2,-2],[2,1,1]], start = 0 Output: []
The loop 1 → 2 → 1 costs -2 + 1 = -1 and can be reached from step 0.
1 <= n <= 2000 <= edges.length <= 2000-1000 <= cost <= 1000Run tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.
Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).
I'm here to help with #465 Cheapest Costs With Refunds. I give hints, never the solution, so you get to solve it yourself. Ask for a hint, select code to ask about it, or press Ask Tuto why on a failing test.
Your first 3 answers need no account. for free to keep asking.