Given are N cities and M roads that travel between the given pair of cities and time it takes to travel that road. Also we are given a list of favourite cities L and a source city S . we have to tell the favourite city which can be reached from source city the fastest(in minimum time)
Solution- Classic Dijkshtra
It was followed by a discussion on runtime complexity and how it was O(V+E log(V))
This went on for a while, since we had a little argument about the complexity of the inner loop.
Then a couple of follow ups
- Early Stoppage conditions
- a fix vertex V to be travelled in the way to favourite city for
- got a little confused and had to take a little help from the interviewer but eventually i told the right solution.
- i made a wrapper function which calls dijkshtra to find dist S-V + dijkshtra to find V- C( favourite city)
Comments (3)


