DSA Master Logo
DSAMaster
Sign InSign Up
mediumDynamic ProgrammingPattern: DP

Minimum Cost Demand Fulfillment Solution

Problem Statement

You are given a directed graph with `N` nodes and `M` edges. Each edge `(u, v)` has an associated `cost_per_unit` and a `capacity`. You are also given a `source_node` and a list of `target_demands`. Each `target_demand` is a pair `[node_id, required_amount]`, indicating that `required_amount` units of a resource must be delivered to `node_id`. The `source_node` has an unlimited supply of resources. Your task is to find the minimum total cost to satisfy all `target_demands` while respecting the `capacity` of each edge. The cost for sending `F` units of resource through an edge `(u, v)` with `cost_per_unit` is `F * cost_per_unit`. If it is impossible to satisfy all demands due to capacity limitations or unreachable target nodes, return -1.

Examples

Example 1:
Input:N = 4, M = 3 edges = [[0, 1, 1, 5], [1, 2, 2, 3], [1, 3, 1, 2]] source_node = 0 target_demands = [[2, 2], [3, 1]]
Output:8
Explanation: To deliver 2 units to node 2: Send 2 units via 0->1->2. Cost = 2 * (1 + 2) = 6. Remaining capacity on (0,1) is 3. To deliver 1 unit to node 3: Send 1 unit via 0->1->3. Cost = 1 * (1 + 1) = 2. Remaining capacity on (0,1) is 2. Total cost = 6 + 2 = 8.
Example 2:
Input:N = 5, M = 6 edges = [[0, 1, 1, 2], [0, 2, 3, 3], [1, 3, 2, 2], [2, 3, 1, 1], [1, 4, 4, 1], [3, 4, 1, 2]] source_node = 0 target_demands = [[3, 2], [4, 1]]
Output:12
Explanation: To meet demands: 1 unit to node 3 via 0->2->3 (cost 4). 1 unit to node 3 via 0->1->3 (cost 3). Then, 1 unit to node 4 via 0->1->4 (cost 5). Total cost = 4 + 3 + 5 = 12.

Constraints

  • `1 <= N <= 100` (Number of nodes)
  • `0 <= M <= N * (N - 1)` (Number of edges)
  • `0 <= cost_per_unit <= 1000` for each edge
  • `0 <= capacity <= 100` for each edge
  • `0 <= required_amount <= 50` for each demand
  • `0 <= source_node, node_id < N`
  • Target nodes in `target_demands` are distinct.
Time: O(F_max * (V_aug * E_aug)) (using SPFA) or O(F_max * (E_aug log V_aug)) (using Dijkstra with potentials and a priority queue), where F_max is the total required flow, V_aug is N + 2 (nodes in augmented graph), and E_aug is M + num_targets + 1 (edges in augmented graph). Space: O(V_aug + E_aug) for storing the graph and residual graph.
This problem is a classic application of the Minimum Cost Maximum Flow (MCMF) algorithm. The graph is augmented with a supersource connected to the given source node, and a supersink connected to all target demand nodes, with edge capacities representing demands. An MCMF algorithm, such as successive shortest path (e.g., using SPFA or Dijkstra with potentials), is then applied to find the minimum cost to send the total required flow from the supersource to the supersink. If the maximum flow achievable is less than the sum of all demands, it's impossible.

Run, Test & Submit Code

Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.

Solve on Interactive Workspace

Tested Solutions

import sys N, M = map(int, sys.stdin.readline().strip().split()) edges = [] for _ in range(M): u, v, cost_per_unit, capacity = map(int, sys.stdin.readline().strip().split()) edges.append([u, v, cost_per_unit, capacity]) source_node = int(sys.stdin.readline().strip()) target_demands = [] for line in sys.stdin: node_id, required_amount = map(int, line.strip().split()) target_demands.append([node_id, required_amount]) graph = [[] for _ in range(N + 1)] for u, v, cost_per_unit, capacity in edges: graph[u].append([v, cost_per_unit, capacity]) def min_cost_demand_fulfillment(N, M, edges, source_node, target_demands): min_cost = [float("inf")] * (N + 1) min_cost[source_node] = 0 for _ in range(N): for u, v, cost_per_unit, capacity in edges: if min_cost[u] != float("inf") and min_cost[u] + cost_per_unit < min_cost[v]: min_cost[v] = min_cost[u] + cost_per_unit total_cost = 0 for node_id, required_amount in target_demands: if min_cost[node_id] == float("inf"): return -1 total_cost += min_cost[node_id] * required_amount return total_cost result = min_cost_demand_fulfillment(N, M, edges, source_node, target_demands) print(result)

Related Problems

Maximum Profit from Scheduled Deliveries
Dynamic Programming•medium
Longest Alternating Subsequence
Dynamic Programming•medium
Max Resource Allocation
Dynamic Programming•easy
Maximize Subset Points
Dynamic Programming•medium