Net Cost With Refunds
EasyAdvanced Graphs
Problem
A freight broker models n warehouses. Each transfers[i] = [u, v, c] is a one-way transfer from u to v with net cost c. Some transfers come with a subsidy, so c can be negative. The network is guaranteed to contain no cycle whose total cost is negative.
Return the minimum total net cost of moving a shipment from source to target. The target is guaranteed to be reachable.
Example 1
- Input:
- n = 4, transfers = [[0,1,4],[0,2,2],[2,1,-3],[1,3,2]], source = 0, target = 3
- Output:
- 1
0 → 2 → 1 → 3 costs 2 - 3 + 2 = 1, cheaper than 0 → 1 → 3 at 6.
Example 2
- Input:
- n = 3, transfers = [[0,1,5],[1,2,-2],[0,2,4]], source = 0, target = 2
- Output:
- 3
Example 3
- Input:
- n = 2, transfers = [[0,1,-7]], source = 0, target = 1
- Output:
- -7
Constraints
- 1 ≤ n ≤ 1000
- 0 ≤ transfers.length ≤ 5000
- -10^4 ≤ c ≤ 10^4
- No negative-cost cycle exists; target is reachable from source.
Hint
Show the first hint
Why is Dijkstra unsafe here? A node that looks final can still be improved by a later negative edge.
Walkthrough
How to approach it
01Clarify before coding
- Can costs be negative? Yes, but there is no negative cycle, so the answer is well defined.
- Are transfers directed? Yes.
- Can source equal target? Yes: the cost is 0.
02Brute force
Enumerate every simple path from source to target with DFS and keep the cheapest.
Cost: Exponential in the worst case: a layered graph has 2^(n/2) simple paths.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.