Solve binary-search knapsack & graph shortest path

Question

Given a sorted list of items, design an efficient solution (using binary search) to achieve the target objective instead of a dynamic-programming knapsack approach. Given a weighted graph provided in a custom input format, build the graph and compute the shortest path between two nodes.

Maximum Items Within Capacity (Binary Search on Prefix Sums)

You are given a list weights of item weights sorted in non-decreasing (ascending) order, and an integer capacity. You want to fit as many items as possible (taking the cheapest items first, i.e. a prefix of the sorted list) without exceeding capacity.

Instead of a dynamic-programming knapsack, build the prefix-sum array of weights and use binary search to find the largest number of items whose total weight is at most capacity. Return that count.

The prefix-sum array is non-decreasing, so binary search runs in O(log n) after the O(n) prefix build.

Example: weights = [1, 2, 3, 4, 5], capacity = 10. Prefix sums are [0, 1, 3, 6, 10, 15]. The largest prefix sum that is <= 10 is 10 (taking the first 4 items: 1+2+3+4 = 10), so the answer is 4.

Constraints

• 0 <= len(weights) <= 10^5
• weights is sorted in non-decreasing order
• 1 <= weights[i] <= 10^9
• 0 <= capacity <= 10^14

Hints

1. Build a prefix-sum array P where P[i] is the total weight of the first i items. P[0] = 0.
2. Because weights are non-negative, P is non-decreasing, so it is sorted — a prerequisite for binary search.
3. Find the largest index i such that P[i] <= capacity. That index i is your answer (number of items taken). bisect_right(P, capacity) - 1 gives it directly.

Shortest Path in a Weighted Graph (Dijkstra)

You are given an integer n (the number of nodes, labeled 0 to n-1) and a weighted undirected graph described by an edge list edges, where each edge is [u, v, w] meaning there is an edge between node u and node v with non-negative weight w.

Build the graph from this custom input format and compute the shortest path distance from source to target using Dijkstra's algorithm. Return the total weight of the shortest path, or -1 if target is not reachable from source.

If source == target, the distance is 0.

Example: n = 5, edges = [[0,1,4],[0,2,1],[2,1,2],[1,3,1],[2,3,5]], source = 0, target = 3. The shortest path is 0 -> 2 -> 1 -> 3 with total weight 1 + 2 + 1 = 4.

Constraints

• 1 <= n <= 10^4
• 0 <= len(edges) <= 10^5
• 0 <= u, v < n
• 0 <= w <= 10^6 (non-negative weights, so Dijkstra applies)
• 0 <= source, target < n

Hints

1. Convert the edge list into an adjacency list. Because the graph is undirected, add each edge in both directions.
2. Use a min-heap (priority queue) keyed by current best distance. Pop the closest unsettled node, then relax its neighbors.
3. Skip stale heap entries: when you pop (d, node), if d is greater than the recorded dist[node], ignore it. Return dist[target], or -1 if it stayed infinite.