3620. Network Recovery Pathways

import java.util.*;

class Solution {
    public int findMaxPathScore(int[][] edges, boolean[] online, long k) {
        int n = online.length;

        List<int[]>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();

        int maxCost = 0;
        for (int[] e : edges) {
            graph[e[0]].add(new int[]{e[1], e[2]});
            maxCost = Math.max(maxCost, e[2]);
        }

        int lo = 0, hi = maxCost, ans = -1;

        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (canReach(graph, online, k, mid, n)) {
                ans = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }

        return ans;
    }

    private boolean canReach(List<int[]>[] graph, boolean[] online, long k, int limit, int n) {
        long[] dist = new long[n];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[0] = 0;

        int[] indegree = new int[n];

        for (int u = 0; u < n; u++) {
            if (u != 0 && u != n - 1 && !online[u]) continue;

            for (int[] e : graph[u]) {
                int v = e[0];
                if (v != 0 && v != n - 1 && !online[v]) continue;
                if (e[1] < limit) continue;
                indegree[v]++;
            }
        }

        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if ((i == 0 || i == n - 1 || online[i]) && indegree[i] == 0) {
                q.offer(i);
            }
        }

        while (!q.isEmpty()) {
            int u = q.poll();

            for (int[] e : graph[u]) {
                int v = e[0];
                int w = e[1];

                if (v != 0 && v != n - 1 && !online[v]) continue;
                if (w < limit) continue;

                if (dist[u] != Long.MAX_VALUE && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                }

                if (--indegree[v] == 0) {
                    q.offer(v);
                }
            }
        }

        return dist[n - 1] <= k;
    }
}

from collections import deque

class Solution:
    def findMaxPathScore(self, edges, online, k):

        n = len(online)

        graph = [[] for _ in range(n)]

        mx = 0

        for u, v, w in edges:
            graph[u].append((v, w))
            mx = max(mx, w)

        def check(limit):

            indegree = [0] * n

            for u in range(n):

                if u != 0 and u != n - 1 and not online[u]:
                    continue

                for v, w in graph[u]:

                    if v != 0 and v != n - 1 and not online[v]:
                        continue

                    if w < limit:
                        continue

                    indegree[v] += 1

            INF = 10 ** 30
            dist = [INF] * n
            dist[0] = 0

            q = deque()

            for i in range(n):
                if (i == 0 or i == n - 1 or online[i]) and indegree[i] == 0:
                    q.append(i)

            while q:

                u = q.popleft()

                for v, w in graph[u]:

                    if v != 0 and v != n - 1 and not online[v]:
                        continue

                    if w < limit:
                        continue

                    if dist[u] != INF and dist[u] + w < dist[v]:
                        dist[v] = dist[u] + w

                    indegree[v] -= 1

                    if indegree[v] == 0:
                        q.append(v)

            return dist[n - 1] <= k

        ans = -1
        lo, hi = 0, mx

        while lo <= hi:

            mid = (lo + hi) // 2

            if check(mid):
                ans = mid
                lo = mid + 1
            else:
                hi = mid - 1

        return ans

class Solution {
public:

    bool check(vector<vector<pair<int,int>>>& graph,
               vector<bool>& online,
               long long k,
               int limit){

        int n=online.size();

        vector<long long> dist(n,LLONG_MAX);
        dist[0]=0;

        vector<int> indegree(n);

        for(int u=0;u<n;u++){

            if(u!=0 && u!=n-1 && !online[u]) continue;

            for(auto &e:graph[u]){

                int v=e.first;
                int w=e.second;

                if(v!=0 && v!=n-1 && !online[v]) continue;
                if(w<limit) continue;

                indegree[v]++;
            }
        }

        queue<int> q;

        for(int i=0;i<n;i++)
            if((i==0||i==n-1||online[i]) && indegree[i]==0)
                q.push(i);

        while(!q.empty()){

            int u=q.front();
            q.pop();

            for(auto &e:graph[u]){

                int v=e.first;
                int w=e.second;

                if(v!=0 && v!=n-1 && !online[v]) continue;
                if(w<limit) continue;

                if(dist[u]!=LLONG_MAX &&
                   dist[u]+w<dist[v])
                    dist[v]=dist[u]+w;

                if(--indegree[v]==0)
                    q.push(v);
            }
        }

        return dist[n-1]<=k;
    }

    int findMaxPathScore(vector<vector<int>>& edges,
                         vector<bool>& online,
                         long long k) {

        int n=online.size();

        vector<vector<pair<int,int>>> graph(n);

        int mx=0;

        for(auto &e:edges){

            graph[e[0]].push_back({e[1],e[2]});
            mx=max(mx,e[2]);
        }

        int lo=0,hi=mx,ans=-1;

        while(lo<=hi){

            int mid=(lo+hi)/2;

            if(check(graph,online,k,mid)){
                ans=mid;
                lo=mid+1;
            }
            else
                hi=mid-1;
        }

        return ans;
    }
};

var findMaxPathScore = function(edges, online, k) {

    const n = online.length;

    const graph = Array.from({length:n},()=>[]);

    let mx = 0;

    for(const [u,v,w] of edges){
        graph[u].push([v,w]);
        mx = Math.max(mx,w);
    }

    function check(limit){

        const indegree = Array(n).fill(0);
        const dist = Array(n).fill(Number.MAX_SAFE_INTEGER);

        dist[0]=0;

        for(let u=0;u<n;u++){

            if(u!==0&&u!==n-1&&!online[u]) continue;

            for(const [v,w] of graph[u]){

                if(v!==0&&v!==n-1&&!online[v]) continue;
                if(w<limit) continue;

                indegree[v]++;
            }
        }

        const q=[];

        for(let i=0;i<n;i++)
            if((i===0||i===n-1||online[i])&&indegree[i]===0)
                q.push(i);

        let head=0;

        while(head<q.length){

            const u=q[head++];

            for(const [v,w] of graph[u]){

                if(v!==0&&v!==n-1&&!online[v]) continue;
                if(w<limit) continue;

                if(dist[u]!==Number.MAX_SAFE_INTEGER &&
                   dist[u]+w<dist[v])
                    dist[v]=dist[u]+w;

                indegree[v]--;

                if(indegree[v]===0)
                    q.push(v);
            }
        }

        return dist[n-1]<=k;
    }

    let lo=0,hi=mx,ans=-1;

    while(lo<=hi){

        const mid=(lo+hi)>>1;

        if(check(mid)){
            ans=mid;
            lo=mid+1;
        }else{
            hi=mid-1;
        }
    }

    return ans;
};