1class Solution {
2    private int nodeCount;
3    private int[][] sortedEdges;
4    private int maxHops;
5
6    /**
7     * Binary searches over the sorted edge weights to find the smallest
8     * weight threshold such that node (n-1) is reachable from node 0
9     * within at most k BFS layers (hops), using only edges whose weight
10     * is no greater than that threshold.
11     */
12    public int minCost(int n, int[][] edges, int k) {
13        this.nodeCount = n;
14        this.sortedEdges = edges;
15        this.maxHops = k;
16
17        // Sort edges by ascending weight so that index in the array
18        // corresponds to a weight threshold.
19        Arrays.sort(edges, (a, b) -> a[2] - b[2]);
20
21        // Binary search on the edge index (i.e., on the weight threshold).
22        int left = 0;
23        int right = edges.length - 1;
24        while (left < right) {
25            int mid = (left + right) >> 1;
26            if (check(mid)) {
27                // Reachable using edges[0..mid]; try a smaller threshold.
28                right = mid;
29            } else {
30                // Not reachable; need a larger threshold.
31                left = mid + 1;
32            }
33        }
34
35        // Verify the final candidate; return its weight if it works.
36        return check(left) ? edges[left][2] : -1;
37    }
38
39    /**
40     * Builds a graph using only edges with index in [0, idx]
41     * (i.e., the idx+1 smallest-weight edges) and performs a
42     * layered BFS from node 0. Returns true if node (n-1) is
43     * reachable within at most maxHops layers.
44     */
45    private boolean check(int idx) {
46        // Adjacency list for the current subgraph.
47        List<Integer>[] graph = new List[nodeCount];
48        Arrays.setAll(graph, i -> new ArrayList<>());
49
50        // Add the idx+1 cheapest edges as undirected connections.
51        for (int i = 0; i <= idx; ++i) {
52            int u = sortedEdges[i][0];
53            int v = sortedEdges[i][1];
54            graph[u].add(v);
55            graph[v].add(u);
56        }
57
58        // Layered BFS: each layer increment counts one extra hop.
59        List<Integer> currentLayer = new ArrayList<>();
60        currentLayer.add(0);
61
62        int distance = 0;
63        boolean[] visited = new boolean[nodeCount];
64        visited[0] = true;
65
66        while (!currentLayer.isEmpty()) {
67            List<Integer> nextLayer = new ArrayList<>();
68            for (int u : currentLayer) {
69                // Target reached: succeed only if within the hop budget.
70                if (u == nodeCount - 1) {
71                    return distance <= maxHops;
72                }
73                // Expand to unvisited neighbors for the next layer.
74                for (int v : graph[u]) {
75                    if (!visited[v]) {
76                        visited[v] = true;
77                        nextLayer.add(v);
78                    }
79                }
80            }
81            currentLayer = nextLayer;
82            ++distance;
83        }
84
85        // Target node never reached within the subgraph.
86        return false;
87    }
88}
89

1class Solution {
2public:
3    int minCost(int n, vector<vector<int>>& edges, int k) {
4        // Sort edges in ascending order by their weight (edge[2]).
5        // This lets us binary search on the edge index: a larger index
6        // means more edges (with greater weights) are available.
7        sort(edges.begin(), edges.end(),
8             [](const vector<int>& a, const vector<int>& b) {
9                 return a[2] < b[2];
10             });
11
12        // check(idx): determine whether, using only the first (idx + 1)
13        // edges (i.e. edges with weight <= edges[idx][2]), there exists a
14        // path from node 0 to node (n - 1) that uses at most k edges (hops).
15        auto check = [&](int idx) -> bool {
16            // Build the adjacency list with the currently allowed edges.
17            vector<vector<int>> graph(n);
18            for (int i = 0; i <= idx; ++i) {
19                int u = edges[i][0];
20                int v = edges[i][1];
21                graph[u].push_back(v);
22                graph[v].push_back(u);
23            }
24
25            // BFS layer by layer from node 0; "dist" tracks the number of
26            // hops from the source to the current frontier.
27            vector<int> currentLevel;
28            currentLevel.push_back(0);
29
30            vector<char> visited(n, 0);
31            visited[0] = 1;
32
33            int dist = 0;
34            while (!currentLevel.empty()) {
35                vector<int> nextLevel;
36                for (int u : currentLevel) {
37                    // Reached the destination: valid only if within k hops.
38                    if (u == n - 1) {
39                        return dist <= k;
40                    }
41                    // Expand to all unvisited neighbors.
42                    for (int v : graph[u]) {
43                        if (!visited[v]) {
44                            visited[v] = 1;
45                            nextLevel.push_back(v);
46                        }
47                    }
48                }
49                // Move to the next BFS layer and increment the hop count.
50                currentLevel.swap(nextLevel);
51                ++dist;
52            }
53            // Destination is unreachable with the allowed edges.
54            return false;
55        };
56
57        int m = edges.size();
58        // Binary search for the smallest edge index that makes check() true.
59        int left = 0, right = m - 1;
60        while (left < right) {
61            int mid = (left + right) >> 1;
62            if (check(mid)) {
63                right = mid;       // mid works, try to find a smaller index.
64            } else {
65                left = mid + 1;    // mid fails, search the larger half.
66            }
67        }
68        // If the final candidate index is valid, return its edge weight as
69        // the minimum cost; otherwise no valid path exists, return -1.
70        return check(left) ? edges[left][2] : -1;
71    }
72};
73

1/**
2 * Finds the minimum possible maximum edge weight along a path from node 0 to node n-1,
3 * such that node n-1 is reachable within at most k hops (BFS levels)
4 * using only edges whose weight is <= that maximum.
5 *
6 * Strategy: sort edges by weight, then binary search on the edge index.
7 * For each candidate index, build a graph using only edges [0..index]
8 * and verify reachability within k levels via BFS.
9 *
10 * @param n     Number of nodes (labeled 0 .. n-1).
11 * @param edges Array of [u, v, weight] triples.
12 * @param k     Maximum allowed number of hops on the path.
13 * @returns     The minimum valid maximum edge weight, or -1 if unreachable.
14 */
15function minCost(n: number, edges: number[][], k: number): number {
16    // Sort edges in ascending order of weight so that index thresholds
17    // correspond to monotonically increasing maximum allowed weight.
18    edges.sort((a, b) => a[2] - b[2]);
19
20    /**
21     * Checks whether node n-1 is reachable from node 0 within k hops,
22     * using only the first (index + 1) lightest edges.
23     *
24     * @param index The highest edge index (inclusive) allowed to be used.
25     * @returns     True if n-1 is reachable in <= k BFS levels, otherwise false.
26     */
27    const check = (index: number): boolean => {
28        // Build an undirected adjacency list from edges[0..index].
29        const graph: number[][] = Array.from({ length: n }, () => []);
30        for (let i = 0; i <= index; i++) {
31            const [u, v] = edges[i];
32            graph[u].push(v);
33            graph[v].push(u);
34        }
35
36        // Standard level-by-level BFS starting from node 0.
37        let queue: number[] = [0];
38        const visited: boolean[] = Array(n).fill(false);
39        visited[0] = true;
40
41        // distance tracks the current BFS level (number of hops from node 0).
42        let distance = 0;
43        while (queue.length > 0) {
44            const nextQueue: number[] = [];
45            for (const u of queue) {
46                // If the target node is reached, succeed only if within k hops.
47                if (u === n - 1) {
48                    return distance <= k;
49                }
50                // Expand to all unvisited neighbors for the next level.
51                for (const v of graph[u]) {
52                    if (!visited[v]) {
53                        visited[v] = true;
54                        nextQueue.push(v);
55                    }
56                }
57            }
58            queue = nextQueue;
59            distance++;
60        }
61
62        // Target node was never reached.
63        return false;
64    };
65
66    // Binary search for the smallest edge index that makes check(index) true.
67    let left = 0;
68    let right = edges.length - 1;
69    while (left < right) {
70        const mid = (left + right) >> 1;
71        if (check(mid)) {
72            // mid works, so the answer is at mid or to its left.
73            right = mid;
74        } else {
75            // mid fails, so a larger threshold is required.
76            left = mid + 1;
77        }
78    }
79
80    // Validate the final candidate; return its weight or -1 if even the
81    // full set of edges cannot satisfy the reachability constraint.
82    return check(left) ? edges[left][2] : -1;
83}
84