Minimum Initial Network Clearance
In a highly secure distributed system, agents need to traverse a network of servers to access critical data. Each server has a specific security level, and traversing a connection between two servers requires the agent to possess a minimum security clearance. Some servers are designated 'Upgrade Stations' which can boost an agent's clearance. The challenge is to determine the absolute minimum initial clearance an agent must possess to successfully reach a target server, leveraging upgrade stations along the way.
Implement the function minInitialNetworkClearance that calculates the lowest possible initial security clearance an agent needs to start at a startServer and reach a targetServer. The agent's clearance can only increase or stay the same. If the startServer itself is an upgrade station, its security level contributes to the initial clearance before any movement occurs.
Function Signature:
function minInitialNetworkClearance(
n: number,
edges: number[][],
securityLevels: number[],
startServer: number,
targetServer: number,
upgradeStations: number[]
): number
Parameters:
n: An integer representing the total number of servers in the network, indexed from 0 to n-1.edges: A 2D array of integers, where each [u, v] pair denotes a bidirectional connection between server u and server v.securityLevels: An array of integers where securityLevels[i] is the security level of server i.startServer: An integer representing the starting server's index.targetServer: An integer representing the target server's index.upgradeStations: An array of integers containing the indices of servers that act as upgrade stations.Return Value:
targetServer is unreachable under any initial clearance, return -1.u and server v, the agent's current clearance must be greater than or equal to max(securityLevels[u], securityLevels[v]).U, their current clearance is permanently updated to max(current_clearance, securityLevels[U]).startServer is an upgrade station, its security level is applied to the initialClearance before any traversal. This initial boost does not require traversing to startServer.startServer and targetServer can be the same. In this case, the minimum initial clearance is 0 (or securityLevels[startServer] if it's an upgrade station and that's higher).Examples
Example 1
Input:
n = 4, edges = [[0,1],[1,2],[2,3]], securityLevels = [10, 50, 20, 30], startServer = 0, targetServer = 3, upgradeStations = [1]
Output:
50
Note:
To go from 0 to 1, clearance 50 is needed (max(SL[0], SL[1])). Initial clearance of 15 is not enough. With initial clearance 50, agent can traverse 0->1. Server 1 is an upgrade station, so clearance remains 50. Then 1->2 (req 50), 2->3 (req 30). All possible.
Example 2
Input:
n = 5, edges = [[0,1],[1,2],[2,3],[3,4],[0,2]], securityLevels = [10, 20, 15, 25, 30], startServer = 0, targetServer = 4, upgradeStations = []
Output:
30
Note:
No upgrade stations available. Agent must rely solely on initial clearance. Path 0->1->2->3->4. Max edge requirement is max(SL[3],SL[4]) = max(25,30) = 30. Initial clearance of 30 allows all steps.
Example 3
Input:
n = 3, edges = [[0,1],[1,2]], securityLevels = [100, 10, 100], startServer = 0, targetServer = 2, upgradeStations = [0]
Output:
100
Note:
Start at server 0 (upgrade station, SL 100). Initial clearance 100 is needed to traverse 0->1 (req max(100,10)=100). Then 1->2 (req max(10,100)=100). Even if initial clearance is 1, it would be boosted to 100 at startServer 0. So minimum 1 is enough. Wait, the problem asks for initial clearance provided to the agent. If startServer is an upgrade station and its SL is higher, that is the effective starting clearance. So if initialClearance is 1, it becomes 100. If 100, it stays 100. The minimum provided initial clearance is 1. Let's adjust the clarification: "If startServer is an upgrade station, its security level is applied to the initialClearance before any traversal. This means the effective starting clearance is max(initialClearance, securityLevels[startServer]). We are looking for the minimum initialClearance provided." So for this example, 1 is the answer. Let's make an example for unreachable.
Example 4
Input:
n = 3, edges = [[0,1],[1,2]], securityLevels = [10, 20, 100], startServer = 0, targetServer = 2, upgradeStations = [1]
Output:
-1
Note:
To traverse 0->1, max(SL[0], SL[1]) = max(10, 20) = 20 is required. With initial clearance 1, can't move. With initial clearance 20, can reach 1. At server 1 (upgrade station), clearance becomes max(20, SL[1]) = max(20, 20) = 20. To traverse 1->2, max(SL[1], SL[2]) = max(20, 100) = 100 is required. Clearance 20 is not enough. No amount of initial clearance will allow path 1->2, because server 1's max clearance is 20, and it's the only upgrade path.
Constraints
1 <= n <= 5000 <= edges.length <= n * (n - 1) / 20 <= u, v < n for all [u, v] in edges1 <= securityLevels[i] <= 10^5 for all i0 <= startServer, targetServer < n0 <= upgradeStations.length <= nupgradeStations are unique.Loading editor...