Challenge
A payment-routing toy model has n venues. A directed edge [u,v,fee] permits a transfer from u to v at a nonnegative integer fee. Find the smallest total fee from source to target using at most max_transfers edges. Return -1 if impossible. One edge is one transfer; intermediary venues are not what the budget counts. Parallel edges and cycles are allowed.
Input and output contract
1 ≤ n ≤ 500; ≤4,000 edges; fees 0..1,000,000; endpoints in 0..n-1; 0 ≤ max_transfers ≤ 30. Source equal to target costs 0 using no edges. k denotes max_transfers. There are no exchange-rate multipliers or hidden costs.
All tests follow this contract. You do not need to validate malformed input. Return the requested result from minimum_cost_trading_path; printed output is not your answer. Standard-library tools are allowed. Implement your solution in Python 3.12.
Target complexity: O(k × (n + e)) time; O(n) auxiliary space
Return values are checked by type. Use the exact function name. Print output is not your answer. Tests have time and memory limits.
Public examples
Arguments
[4, [[0, 1, 1], [1, 2, 1], [2, 3, 1], [0, 3, 8]], 0, 3, 2]
Expected return
8
Arguments
[4, [[0, 1, 1], [1, 2, 1], [2, 3, 1], [0, 3, 8]], 0, 3, 3]
Expected return
3
Arguments
[1, [], 0, 0, 0]
Expected return
0
Hint
Let the next DP layer read only the previous layer. In-place relaxation could accidentally use several transfers in one round.
The worked solution unlocks after completion, or with Premium access.