3924. Minimum Threshold Path With Limited Heavy Edges

There is an undirected weighted graph with n nodes labeled from 0 to n - 1.

The graph is represented by a 2D integer array edges, where each edge edges[i] = [u_i, v_i, w_​​​​​​​i] indicates that there is an undirected edge between nodes u_i and v_i with weight w_​​​​​​​i.

You are also given integers source, target and k.

A threshold value determines whether an edge is considered light or heavy:

• An edge is light if its weight is less than or equal to threshold.
• An edge is heavy if its weight is greater than threshold.

A path from source to target is valid if it contains at most k heavy edges.

Return the minimum integerthreshold such that at least one valid path exists from source to target. If no such path exists, return -1.

int uf[101010];
int find(int u) {
    return uf[u] == u ? u : uf[u] = find(uf[u]);
}
void uni(int u, int v) {
    int pu = find(u), pv = find(v);
    uf[pu] = uf[pv] = min(pu,pv);
}
class Solution {
    bool helper(int n, vector<vector<int>>& E, int u, int v, int k, int m) {
        iota(begin(uf), end(uf), 0);
        vector<vector<int>> adj(n);
        for(auto& e : E) {
            if(e[2] <= m) uni(e[0],e[1]);
            else {
                int u = find(e[0]), v = find(e[1]);
                if(u == v) continue;
                adj[u].push_back(v);
                adj[v].push_back(u);
            }
        }
        vector<bool> vis(n);
        queue<int> q;
        auto push = [&](int u) {
            if(!vis[u]) q.push(u), vis[u] = true;
        };
        push(find(u));
        for(int i = 0; i < k; i++) {
            int qsz = q.size();
            while(qsz--) {
                int u = q.front(); q.pop();
                for(auto& v : adj[u]) push(v);
            }
        }
        
        return vis[find(v)];
    }
public:
    int minimumThreshold(int n, vector<vector<int>>& edges, int source, int target, int k) {
        if(source == target) return 0;
        iota(begin(uf), end(uf), 0);
        for(auto& e : edges) uni(e[0], e[1]);
        if(find(source) != find(target)) return -1;
        sort(begin(edges), end(edges), [](auto& a, auto& b) {
            return a[2] < b[2];
        });
        vector<int> S{0};
        for(auto& e : edges) if(S.size() == 0 or S.back() != e[2]) S.push_back(e[2]);
        int l = 0, r = S.size() - 2, res = S.back();
        while(l <= r) {
            int m = l + (r - l) / 2;
            bool ok = helper(n, edges,source,target,k,S[m]);
            if(ok) {
                res = S[m];
                r = m - 1;
            } else l = m + 1;
        }
        return res;
    }
};