  We study a class of reachability problems in weighted graphs with constraints
on the accumulated weight of paths. The problems we study can equivalently be
formulated in the model of vector addition systems with states (VASS). We
consider a version of the vertex-to-vertex reachability problem in which the
accumulated weight of a path is required always to be non-negative. This is
equivalent to the so-called control-state reachability problem (also called the
coverability problem) for 1-dimensional VASS. We show that this problem lies in
NC: the class of problems solvable in polylogarithmic parallel time. In our
main result we generalise the problem to allow disequality constraints on edges
(i.e., we allow edges to be disabled if the accumulated weight is equal to a
specific value). We show that in this case the vertex-to-vertex reachability
problem is solvable in polynomial time even though a shortest path may have
exponential length. In the language of VASS this means that control-state
reachability is in polynomial time for 1-dimensional VASS with disequality
tests.
