I'm looking for a solution to the following problem, related to shortest path.
You are given a directed Graph $G = (V,E)$, source $s$, targets $t_1, t_2, \cdots , t_k$ and costs $c_{ij}$ for traveling edge $\{i,j\}$. Now, I want to know the shortest paths from $s$ to $t_1, \cdots , t_k$. But, if a vertext $v_i$ (not source or targets) is used then we have an additional cost of $C$. Note that if two paths use the same vertext $v_i$, the cost $C$ is only paid once.
I hope someone can help me with this. I've been struggling with this problem for quite a while now.
Thanks in advance,
Sjoerd