Finding an exactly weighted st-path in a digraph
This problem is NP-complete.

The "$\in$ NP"-part is trivial.

For the NP-hard part we reduce directed hamiltonian path:


  Given a directed graph $G=(V,E)$ and two vertices $v_1,v_2\in V$, is there a path from $v_1$ to $v_2$, that visits each vertex exactly once?


For the reduction we keep $G$, $v_1$, and $v_2$ and number the nodes from $1$ to $n$, so that $v_2$ gets the number $n$. Then we assign each edge from node $i$ to node $j$ the weight $2^n+2^i$ and ask for a path of weight $n\cdot 2^n-1$.

It is easy to compute, that a hamiltonian path will have the correct weight. 

For the other direction note that any path that takes $n$ steps or more would have a weight above $n\cdot 2^n$ and thus be invalid. A path that only takes $n-2$ or fewer steps on the other hand would have a weight below $(n-1)\cdot 2^n$, which is also invalid. So any valid path will have a length of $n-1$.

Furthermore the required weight has the bit for $2^i$ set to $1$ for each $0&lt;i&lt;n$. In order to achieve this without visiting node $i$, we would need to visit node $i-1$ (or a node with a smaller number) multiple times. But we only have $n-1$ steps to set $n-1$ bits. So only hamiltonian paths can achieve the correct weight.

The reduction works in polynomial time, since the size of the binary encoding of the weights and target is linear in the number of nodes.