bristy1588's blog

By bristy1588, 9 years ago, In English

Here is the problem: http://acm.timus.ru/problem.aspx?space=1&num=1930

Basically we have to find the shortest path form one node to another where the weights of the edges are 0 or 1.

Here is my code: http://paste.ubuntu.com/1527659/

Can anyone please help?

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This is probably not the answer but, my first bfs solution was very similar to yours and it also got WA in test case 6. Then the DP solution passed. I am not sure, but may be we are missing something silly in our bfs implementation. If I can figure out the bug I'll share it with you.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks Xerxes.. By the way, Can i know your real name?

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      sure,I am Pallab. You know wasi and fahim bhaiya, right? They are my friends. :)

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes i know know them! Now I know you as well :)

»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

http://paste.ubuntu.com/1531247/ ... changed one line of your code, this will get AC :) why ? just debug your code with the following case, & you'll understand :

3 2 2 1 2 3 1 3