Path in a graph with durations
This solution is by Gerhard Woeginger.

In order to prove that this problem belongs to NP,
we provide a polynomial-size certificate,
and then we show how to check it in deterministic polynomial time.

The certificate is just the following:
a set of integers $\{x_{u,v}\mid (u,v)\in E\}$.
Intuitively, $x_{u,v}$ is the number of times the solution path
traverses $(u,v)$.

We now describe the
verification algorithm.


We consider the subset $E'$ of edges of $G$, $E':=\{(u,v)\in E\mid x_{u,v}&gt;0\}$. We check whether $E'$ induces a strongly (undirected)
connected subgraph of $G$.
We check whether 


$\sum_{(u,v)\in E'} x_{u,v}=\sum_{(v,w)\in E'} x_{v,w}$, for all $v \in V\setminus\{s,t\}$;
$\sum_{(u,s)\in E'} x_{u,s}=\sum_{(s,w)\in E'} x_{s,w}-1$;
$\sum_{(u,t)\in E'} x_{u,t}=\sum_{(t,w)\in E'} x_{t,w}+1$.

For all $v \in V\setminus\{s\}$, we define $y_v:=\sum_{(u,v)\in E'} x_{u,v}$, i.e., the number of times the solution path gets into $v$. Moreover, 
$y_s := \sum_{(s,u)\in E'} x_{s,u}$.
We check whether there exist real values $z_v$, for every $v \in V$, such that


$d_{min}(v)\cdot y_v \leq z_v \leq d_{max}(v)\cdot y_v$ (here $d_{min}(v)$ and $d_{max}(v)$ denote resp. the lower and the upper
bound of the rational interval $d(v)$), and
$\sum_{v \in V} z_v = h$.



We now sketch the correctness:

Steps 1. and 2. together check that the values $x_{u,v}$ for the arcs specify
a directed Eulerian path from $s$ to $t$ (we refer to http://www.maths.manchester.ac.uk/~mrm/Teaching/DiscreteMaths/LectureNotes/EulerianMultigraphs.pdf)

Steps 3. and 4. calculate $z_v$, for all $v\in V$, which is the total waiting time of the path on the node $v$. We observe that the (in)equalities of step 4.
form a linear program (LP), which can be solved in deterministic polynomial time (e.g., using the ellipsoid algorithm).