We are given a graph with $n$ vertices, $m$ edges, and path edge costs of $x$. For vertices without a direct path that are distant exactly one neighbor, we can add new edge with edge cost $y$. Our task is to find shortest path (i.e minimum cost) between the start vertex and all others vertices.
I have developed an algorithm, but I would like to create something faster than adding edges to the graph (via breadth-first search) and Dijkstra's algorithm. Here are a couple examples:
Example 1 Input: For $x=3$, $y=1$
Possible $y$ paths included:
Output: cost of shortest path from start node to node $i$ (assume that from start node to start node is 0)
Example 2 Input: For $x=3, y=2$