Constrained Shortest Path — Cost + Resource

Pseudo-polynomial DP

// dp[u][t] = min cost to reach u using resource exactly t
for each vertex u in topo order (or via BFS)
  for each edge (u, v, cost, res)
    for each t from B down to res
      dp[v][t] = min(dp[v][t], dp[u][t - res] + cost)

Complexity

O(E × B). Pseudo-polynomial: exponential in log(B).

Lagrangian relaxation

Add penalty λ × (used_resource - B) to objective. Binary search on λ. Get approximate answer.

FPTAS

Fully polynomial approximation exists via rounding costs. Provable (1+ε) approx.