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 )
Your idea is wrong because you don't have to pay twice if you use the edge twice.
It looks like it can be solved using min SPT ??
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.
But MST gives WA :( Solution
I'll solve this problem on my next stream.