An events company sets up n booths numbered 0 to n - 1 and gets quotes quotes[i] = [a, b, price] for running a cable between booths a and b. Cables work both ways.
Write withinBudget(n, quotes, budget) that returns true if every booth can be connected for a total of at most budget, and false otherwise (including when the booths can't be connected at all).
Input: n = 4, quotes = [[0,1,1],[1,2,2],[0,2,4],[2,3,3],[1,3,5]], budget = 6 Output: true
The cheapest way to connect all booths costs exactly 6.
Input: n = 4, quotes = [[0,1,1],[1,2,2],[0,2,4],[2,3,3],[1,3,5]], budget = 5 Output: false
No set of cables connecting all four booths costs less than 6.
1 <= n <= 100000 <= quotes.length <= 500001 <= price <= 10^40 <= budget <= 10^9Run 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 #472 Is the Cabling Budget Enough?. 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.