Hey i have worked with graph theory before and this question i had made a solution very very very slow , so i am trying to find a fast solution , please help me , thnx in advanced , here goes quesiton:-
Link: Contest Page | CodeChef
This is a two-part problem. First you have to determine if both the goal node and the start node are part of the same connected graph. You can do this with simple set theory operations.
Second, IFF the goal node and start node are part of the same connected graph, you need to find the least cost path between them. There are many possible ways to do this but the fastest one is probably going to be a bidirectional search.
Which part are you needing help with? (And which programming language are you using? I recommend an object-oriented language for set or graph theory problems.)
It can be solved by 2 parts.
- Using disjoint set data structure to find if start and end point belong to the same set.
- Using BFS to find the minimum number of steps.
hope this helps.
what have you tried till now? Also post your code to get some suggestions
1stly make your post more readable. Note that you get a new line if you press enter twice while typing the post.
(As Tarun Mentioned) Then you will get for what you do! So far what have you done on that problem. Share your taughts and your code. Then you will get better help.
If the problem is already available elsewhere on the internet, then it is best to have a link given to that instead of posting the whole content here. That will save the typesetting issues also for you.
1 Like
okay , i got it all and i m posting little more details .
i am using c++ , i planned to use BFS algorithm , but i am not sure , how to count the length , maybe its easy but i am not getting it though , i am a beginner , very beginner . So it would be nice , if someone could tell me code , or part of code , my last algorithm was using DFS algorithm so it was very slow , i hope you can now help me @cmdrsunshine .
Thankyou in advanced .