Path of exact cost in edge labelled DAG? Given edge labelled directed acyclic graph with edge labels $w_i \in \mathbb{N}$ the cost of a path is the sum of the labels.

The problem is:


  Find a path from $s$ to $t$ with cost $a$.


I suppose this is NP-hard.

Some questions:


Would putting a bound $\max w_i &lt; C$ make the problem easier?
What are the best algorithms for this?
Is the problem NP-complete?


Update
What about this modification of Number: 63 Shortest Weight-Constrained Path

To each edge associate second label weight $r_i \in \mathbb{N}$. The weight of a path is the sum of $r_i$.

Assume (possibly small) bound $C$ of the costs $w_i$ and solve:

$cost = a$ and $weight &lt; K$.

Would it be still polynomial in $n,m,C$ or NP-hard instances exist (one can assume positive labels if this helps)?
Yes, it's NP-complete, by a reduction from subset sum. It's easiest to see using a multigraph: make a directed path, double each edge, and make one of the two doubled edges have cost zero, then cost $a$ can be achieved if and only if it is the sum of some subset of the weights of the nonzero edges. If you don't like multigraphs, subdivide the edges.

If you assume that $\max w_i&lt;C$ then there's a dynamic programming algorithm with time $O(mnC)$: just process the nodes in a topological ordering, and for each node calculate the set of path lengths by which it can be reached from $s$.