suraj021's blog

WA in TimusOJ
By suraj021, 9 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

Comments Comments (5)
| Write comment?
»
9 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.

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

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

    → Reply
    • »
      »
      »
      9 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.

      → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I'll solve this problem on my next stream.

→ Reply