Oyo Key Property Collection
Oyo is undergoing a critical audit of its property portfolio. A specialized audit team needs to visit a specific set of "key properties" across a city to collect unique audit artifacts. These artifacts are crucial for compliance. Some properties, however, have restricted access and can only be audited if a particular prerequisite artifact has already been collected. The audit team starts at a central depot and must efficiently collect all required artifacts, then return to the depot, minimizing total travel time.
You are tasked with implementing a function findMinAuditTime that calculates the minimum total travel time required for the audit team to:
startNodeId (depot).keyProperty to collect its unique keyId.prerequisite rules, meaning a property requiring keyX cannot be entered until keyX has been collected.startNodeId after all keys have been collected.If it's impossible to collect all keys and return, the function should return -1.
The function signature is:
function findMinAuditTime(n: number, roads: number[][], startNodeId: number, keyProperties: number[][], prerequisites: number[][]): number
n: An integer representing the total number of locations in the city, indexed from 0 to n-1.roads: A 2D array of integers, where roads[i] = [u, v, time] indicates a one-way road from location u to location v that takes time minutes to travel.startNodeId: An integer representing the starting and ending location (the depot).keyProperties: A 2D array of integers, where keyProperties[i] = [nodeId, keyId] indicates that location nodeId provides the unique artifact keyId. keyIds are 0-indexed and unique.prerequisites: A 2D array of integers, where prerequisites[i] = [nodeId, requiredKeyId] indicates that nodeId can only be entered if requiredKeyId has already been collected.-1 if it's impossible.keyIds are distinct and range from 0 to K-1, where K is the total number of unique keys (i.e., keyProperties.length).keyProperty is instantaneous (does not add to travel time).startNodeId itself has a prerequisite, it must be satisfied before starting the audit, which is impossible. Assume startNodeId never has a prerequisite.Examples
Example 1
Input:
n = 3, roads = [[0,1,10], [1,2,5], [2,0,12]], startNodeId = 0, keyProperties = [[1,0], [2,1]], prerequisites = []
Output:
27
Note:
Start at 0. Path: 0 -> 1 (cost 10, collect key 0). State: (node 1, keys {0}). Then 1 -> 2 (cost 5, collect key 1). State: (node 2, keys {0,1}). Then 2 -> 0 (cost 12, return to depot). Total cost: 10 + 5 + 12 = 27.
Example 2
Input:
n = 4, roads = [[0,1,10], [1,2,5], [0,3,1], [3,2,1], [2,0,12]], startNodeId = 0, keyProperties = [[1,0], [2,1]], prerequisites = [[2,0]]
Output:
27
Note:
Start at 0. Node 2 requires key 0. Fastest path to collect key 0 is 0 -> 1 (cost 10). Now at node 1 with key 0. Then 1 -> 2 (cost 5). At node 2, collect key 1. All keys collected. Then 2 -> 0 (cost 12). Total: 10 + 5 + 12 = 27. Path 0->3->2 is not valid for node 2 as key 0 is not yet collected.
Example 3
Input:
n = 3, roads = [[0,1,10], [1,0,10]], startNodeId = 0, keyProperties = [[1,0], [2,1]], prerequisites = []
Output:
-1
Note:
Node 2 is unreachable from any other node. It's impossible to collect key 1.
Constraints
1 <= n <= 500 <= roads.length <= 5000 <= u, v < n, u != v1 <= time <= 10000 <= startNodeId < n0 <= keyProperties.length <= 10 (let K = keyProperties.length)0 <= keyId < KkeyId in keyProperties is unique.0 <= prerequisites.length <= K0 <= requiredKeyId < Kroads. Duplicate roads [u, v, time] are possible; consider the minimum time if multiple paths exist directly between u and v.Loading editor...