suraj021's blog

By suraj021, 5 years ago, In English,

I am solving problem Electrification Pan in TimusOJ. My approach was to calculate shortest path between any pair using Floyd warshall algo and then calculate min cost from each vertex to the vertices with power station and add them . But unfortunately it gives WA. My Solution in Ideone. Please point out my mistake :) Thanks UPD: Still I cannot solve this problem( 19/08/2015 )

 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Your idea is wrong because you don't have to pay twice if you use the edge twice.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    It looks like it can be solved using min SPT ??

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

      Yes, it can be solved easily with MST, I really don't know why the limits are so low, it is solvable with n = 1000, or n = 10^5 and m = 10^5.

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I'll solve this problem on my next stream.

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

    This problem is nice. Whenever you solve it please update me :) Thank you.