Gas Station Problem - Dijkstra's Algorithm variation
We note that we can assume that the source node has a gas station with refilling cost as $0$, even if it doesn't. It just makes the algorithm cleaner, as we start out with a full tank, and we note that no optimal solution is ever going to come back to the source again and refill. Similarly, we also assume that the $\text{target}$ also has a gas station with some arbitrary cost of refilling - the cost here wouldn't matter. So in effect, we set $S = S \cup \{\text{source, target}\}$.

In the first phase of the algorithm, for every $s \in S$, we want to find all the other towns in $S$ that we can reach without refueling, if we start out with a full tank from $s$. For this, we can take two approaches:


Run Floyd–Warshall using $w(u, v)$ as the weight of every edge, to find the shortest distance from any town to any other. Now, for every $s \in S$, we iterate through every other $t \in S$ and if the shortest distance from $s$ to $t$ is $\leq k$, then we can reach $t$ from $s$ without refueling. So we create a new graph $G'$, whose vertex set is $S$, and add a directed edge $(s, t)$ with a weight of $c(s)$. This approach takes $\mathcal{O}(|T|^3)$ time and $\mathcal{O}(|T|^2)$ space.
Another way to construct the same $G'$, would be to start a Dijkstra's from every $s \in S$, and stop when the distance is more than $k$, which in the worst case wouldn't help our complexity. This approach would require $\mathcal{O}(|S| \times (|R| + |T|\log|T|)$ time and $\mathcal{O}(|T|^2)$ space.


The second approach is asymptotically better than the first one, but the first one is easier to implement. So you can decide which fits your needs better.

Now on to the second phase of the algorithm, where we have the graph $G'$ with us, which again is a directed weight graph, but now the weights are costs of refilling. So all we have to do is run a Dijkstra's on this graph starting from $\text{source}$. The answer is the shortest distance to $\text{target}$.

So the total algorithm needs $\mathcal{O}(|S| \times (|R| + |T|\log|T|)$ time and $\mathcal{O}(|T|^2)$ space.