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.

  • 1
    $\begingroup$ What have you tried? Where did you get stuck? $\endgroup$
    – phan801
    Feb 10, 2019 at 9:31
  • $\begingroup$ 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. $\endgroup$ Feb 10, 2019 at 9:47
  • $\begingroup$ geeksforgeeks.org/… $\endgroup$ Feb 10, 2019 at 10:06

1 Answer 1


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.

I'll let you figure out why this works.

  • 1
    $\begingroup$ The graph that I construct is directed. You can only go forward. $\endgroup$ Oct 20, 2020 at 20:56
  • $\begingroup$ Yes I realised that later, thank you! $\endgroup$ Oct 21, 2020 at 4:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.