Minimize the Maximum Edge Weight of Graph

Challenge Points: 20

Level: Medium

You are provided with a directed weighted graph containing n nodes numbered from 0 to n - 1, and an integer threshold.
The graph is represented by a list of edges, where each edge is described as edges[i] = [Ai, Bi, Wi], meaning there is a directed edge from node Ai to node Bi with weight Wi.

Your task is to remove some edges (if necessary) so that the resulting graph satisfies the following constraints:

Every node must be able to reach node 0.
The maximum edge weight in the remaining graph should be as small as possible.
Each node can have no more than threshold outgoing edges.

Return the minimum achievable maximum edge weight after performing removals.
If it’s impossible to meet all the conditions, return -1.

Example 1:

Input: n = 4, edges = [[1,0,3],[2,1,2],[3,1,4],[2,0,5]], threshold = 2

Output: 4

Explanation:

By removing the edge 2 -> 0 (weight 5), the remaining graph still allows all nodes to reach node 0, and the maximum edge weight becomes 3.

Example 2:

Input: n = 4, edges = [[0,1,2],[1,2,3],[2,3,1],[3,0,4]], threshold = 1

Output: 4

Explanation:

Since each node can have at most one outgoing edge, it’s impossible to make all nodes reach node 0.

Example 3:

Input: n = 5, edges = [[1,0,2],[2,0,1],[3,2,3],[4,3,2],[4,0,5]], threshold = 2

Output: 3

Explanation:

We can remove edge 4 -> 0 (weight 5). The maximum edge weight left is 2, and all nodes can still reach node 0.

to Continue

Accepted:

Submission:

Report an issue

Code

You need toto run or submitYou need toto run or submit

Test Case

Test Result