# Shortest path from source to all vertices, but with some wildcards

Here is problem in Sprinklr Interview Experience | Set 5 (On campus – FTE for Product Engineer).

You are given a graph of $$n$$ nodes with $$m$$ bidirectional edges. Each edge has some value associated with it. Vertex $$1$$ is source vertex. You have $$K$$ wildcards. In the path from vertex $$1$$ to vertex $$i$$ ($$2 \leq i \leq n$$), you can use at most $$K$$ wildcards while traversing. When you use a wildcard on an edge, you can pass that edge in summing the cost of path (i.e., value of that edge will be $$0$$ if you use a wildcard on an edge). Note: You can use at most $$K$$ wildcards from vertex $$1$$ to vertex $$2$$. Now you can again use at most $$K$$ wildcards from vertex $$1$$ to vertex $$3$$ and so on to vertex $$n$$. In other words, you can use at most $$K$$ wildcards in each path from source to destination. You have to find minimum distances from node $$1$$ to all other nodes in graph.

Constraints: $$1 \leq n, m \leq 500000, 1 \leq K \leq 15$$

Expected Approach: DP with shortest path algorithms on graph.

What I am doing is that, we can choose $$k$$ edges from $$m$$ edges in $$\binom{m}{k}$$ ways. And for each case find shortest path, but that will be too much time complexity.

• What have you tried? Where did you get stuck? Feb 10, 2019 at 9:31
• I tried this,choose edges k from m,which is m choose k. Remove them and find shortest path for each case.that is too much time complexity. Feb 10, 2019 at 9:47
• geeksforgeeks.org/… Feb 10, 2019 at 10:06

Take $$K+1$$ copies of your graph. For each edge $$(x,y)$$ and for each $$i \in \{1,\ldots,K\}$$, connect the $$i$$'th copy of $$x$$ to the $$(i+1)$$'th copy of $$y$$ with a zero weight edge. Also connect the $$i$$'th and $$(i+1)$$'th copies of each vertex with a zero weight edge. Now calculate the minimum distance between vertex 1 on the first copy to all vertices in the last copy.