Ai != Bi

1 <= Wi <= 10^6

There may be multiple edges between a pair of nodes, but they must have unique weights.

Solution

Method 1 – Binary Search + BFS

Intuition

To minimize the maximum edge weight, we can use binary search on the possible edge weights. For each candidate maximum weight, we check if it's possible to keep only edges with weight ≤ candidate, prune outgoing edges to threshold per node, and ensure node 0 is reachable from all other nodes.

Approach

Use binary search on the maximum edge weight from 1 to the largest edge weight.
For each candidate, build a graph keeping only edges with weight ≤ candidate.
For each node, keep only the threshold smallest outgoing edges.
Use BFS or DFS to check if node 0 is reachable from all other nodes (reverse graph).
If possible, update answer and try lower candidate; else, try higher.
If not possible for any candidate, return -1.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int minimizeMaxEdgeWeight(int n, vector<vector<int>>& edges, int threshold) {\n        int lo = 1, hi = 0;\n        for (auto& e : edges) hi = max(hi, e[2]);\n        int ans = -1;\n        while (lo <= hi) {\n            int mid = lo + (hi - lo) / 2;\n            vector<vector<pair<int,int>>> g(n);\n            for (auto& e : edges) {\n                if (e[2] <= mid) g[e[0]].emplace_back(e[1], e[2]);\n            }\n            for (int i = 0; i < n; ++i) {\n                sort(g[i].begin(), g[i].end(), [](auto& a, auto& b){ return a.second < b.second; });\n                if (g[i].size() > threshold) g[i].resize(threshold);\n            }\n            vector<bool> vis(n);\n            queue<int> q;\n            q.push(0); vis[0] = true;\n            while (!q.empty()) {\n                int u = q.front(); q.pop();\n                for (auto& [v, w] : g[u]) {\n                    if (!vis[v]) { vis[v] = true; q.push(v); }\n                }\n            }\n            bool ok = true;\n            for (int i = 0; i < n; ++i) if (!vis[i]) ok = false;\n            if (ok) { ans = mid; hi = mid - 1; }\n            else lo = mid + 1;\n        }\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> minimizeMaxEdgeWeight</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> n</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><

Related Tags