Expedited Creative Asset Delivery
Adobe Creative Cloud empowers millions of users globally, and efficient asset delivery is critical for a seamless experience. Imagine a network of Adobe data centers (nodes) interconnected by various routes (edges). Each route has an associated latency (time) and a usage cost. Some routes might offer faster delivery but at a higher cost. Your task is to optimize asset delivery by finding the fastest path from a source data center to a destination data center, ensuring the total cost of the path does not exceed a specified budget. This problem is crucial for balancing performance with operational expenditure in a large-scale distributed system.
Implement a function findMinTimeWithBudget that determines the minimum possible time to transfer an asset from a source data center to a destination data center, given a maximum budget.
edges.-1 if no such path exists within the given budget.The function signature is findMinTimeWithBudget(n: number, edges: number[][], source: number, destination: number, budget: number): number.
n: An integer representing the total number of data centers. Data centers are labeled from 0 to n-1.edges: An array of arrays, where each inner array [u, v, time, cost] represents a directed connection from data center u to data center v.
u, v: Integers representing the source and destination data centers of the connection.time: An integer representing the latency (time in milliseconds) to traverse this connection.cost: An integer representing the operational cost to use this connection.source: An integer representing the starting data center.destination: An integer representing the target data center.budget: An integer representing the maximum total operational cost allowed for the entire path.Return Value:
An integer representing the minimum time required to deliver the asset from source to destination within the budget. Return -1 if no such path exists.
u == v) or multiple edges between the same pair of data centers. If multiple edges exist, your algorithm should naturally find the optimal one based on the objective.source to destination that satisfies the budget constraint, return -1.source is the same as destination, the minimum time is 0 and cost is 0.budget is 0, only paths with zero total cost are allowed. If an edge has cost=0, it can be used.Examples
Example 1
Input:
n = 3, edges = [[0,1,10,1],[1,2,10,1],[0,2,100,10]], source = 0, destination = 2, budget = 2
Output:
20
Note:
Consider paths from 0 to 2:
Example 2
Input:
n = 2, edges = [[0,1,5,5],[0,1,1,10]], source = 0, destination = 1, budget = 8
Output:
5
Note:
There are two direct paths from 0 to 1:
Example 3
Input:
n = 3, edges = [[0,1,10,1],[1,2,10,1],[0,2,100,10]], source = 0, destination = 2, budget = 0
Output:
-1
Note:
With a budget of 0, only paths with a total cost of 0 are allowed. All given edges have a cost of 1 or 10, meaning no path can be formed without exceeding the budget. Thus, no path exists within budget.
Constraints
1 <= n <= 1000 <= edges.length <= n * (n - 1)edges[i].length == 40 <= u, v < n1 <= time, cost <= 1000 <= source, destination < n0 <= budget <= 1000time and cost values are non-negative.N*Budget states are fine).Loading editor...