I was reading http://arxiv.org/abs/1201.4995, and thought back to a game I used to play,
which is close to being covered by part (c) of "Metatheorem 2" on page 4 of that paper.
(The difference is that the game's version of toll roads only charge for the first passage.)
What is the computational complexity of the following problem:
For a graph $G$ whose vertices have non-negative integer weights, for vertices $s$ and $t$, is there a
path from $s$ to $t$ such that the sum of the weights of the vertices (including $s$) reached at any given point along it is always greater than the number of distinct edges traversed to get to that point?
(The vertices are not counted with multiplicity either.)