[C++] Dijkstra | Track time taken instead of visited nodes | Picture illustration
This problem is very similar to 787. Cheapest Flights Within K Stops\nIn dijkstra algo, we keep track of minimum distance, and we stop traversing node once it i
This problem is very similar to **787. Cheapest Flights Within K Stops**\nIn dijkstra algo, we keep track of minimum distance, and we stop traversing node once it is visited.\n\nWe do so, because we know that once a node is processed with minimum distance, no matter what other routes we take, it will no more be minimum.\n\nWe can take similar idea here. The condition is that, we are allowed to visit a node as long as we can visit within `maxTime` minutes.\n\nLet\'s take an example below-\n\nFor the simplicity, I have taken time spent for each path as per the below graph, and `maxTime` as 5.\n![image](https://assets.leetcode.com/users/images/b401983f-c103-4fa4-bc80-d23c3831c6b0_1628271830.0042944.png)\n\nFrom the above, there are two possible paths [sky, blue] to reach destination. \nEach path will take 5 mins, and cost of sky path will be 10, where as cost of blue path will be 9.\n\nNotice that, to reach node-1 from node-0, we can take sky or blue path. \nAt first glance, we can pick sky path, because it will give us minimum cost(1 + 5) as compared to blue path(1 + 2 + 5).\n\nBut later on, sky path will be more costlier to us than blue path. So we should be considering every possible path as long as the total time spent doesn\'t exceed the `maxTime`.  \n\nWhenever we notice that the new time spent to reach a particular node exceeds the previous time spent, we will stop considering the node.\n\nRest, it will be as similar as dijkstra algo.\n\n<iframe src="https://leetcode.com/playground/NLiZpaAy/shared" frameBorder="0" width="900" height="700"></iframe>\n\nTime and space complexity will be same as dijkstra algo.
[]