I came across this problem and I submitted a DFS solution and it got AC.
But it took way lesser time than I expected it to take.
Like...
Forgetting all the vertices which can't be reached, at every level we have 10 new vertices and the depth is 1000 in the worst case.
Wouldn't a DFS have a huge number of steps and this code took around 30ms.
Any reasoning as to why my reasoning is wrong would be highly appreciated :)
Your code works fast enough due to fact that choosing the smallest possible weight is always optimal. So if the answer is "YES", then your code works in linear time, but I'm not really sure why this works fast if the answer is "NO"