senshi2504's blog

Shortest Path with fluctuating roads
By senshi2504, history, 7 years ago, In English

https://www.hackerearth.com/practice/algorithms/graphs/shortest-path-algorithms/practice-problems/algorithm/mancunian-goes-to-the-derby/description/ I am facing it tough to understand the editorial of this problem . I know it'll sound really simple for most of you . So can someone please explain the editorial to me , or tell me their own way of going about this problem. Any help is appreciated :)

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

You can use bfs to get minimal time you need to reach point N. Code

→ Reply
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I am the setter of this problem. What did you not understand in the editorial? The crux is that the direction of each edge depends on the parity (odd or even) of the current time. So, for each vertex, we create two nodes to consider both cases. If you could perhaps explain in some more detail exactly the part which is unclear, maybe I could help. :)

→ Reply