$st$-path with fewest leaving edges
Suppose input graph is simple (without parallel edges), now, If you solve your problem, you can check existence of Hamiltonian path, actually if s-t path of cost zero for some pair exists means there is Hamiltonian path and you can check this for all pair of vertices as (s,t), so you are unlucky to have polynomial time algorithm except $P=NP$.