AC answer:
Cost: 24
Cost: 25

Thanks
answer is 24，25.

My 0.093  N square solution:

1) Compute MST with Kruskal in E logE.
2) For each pair of vertices in MST compute dp[u][v] the cost of largest edge on path from u to v. This can be done by calling N depth first searches. DFS runs in O(E) and there is N - 1 edge in a MST. So this step takes (N^2) time.
3) For each edge (u, v) that isn't in a MST try to relax answer with { MST_COST - dp[u][v] + weight(u, v) }. This step is done in O(E).

So, the running time of this solution is O(ElogE + E + N^2) = O(N^2).

Dude, the same to me :((

I've got a wa ,too.
I need test data to find question.

4 6
1 2 1
1 3 5
3 4 1
4 2 3
4 1 8
2 3 0

Have a try!
The right answer is 2 4
At first I forgot something and failed at #11

4 6
1 2 1
1 3 5
3 4 1
4 2 3
4 1 8
2 3 0
is this test #11?

Tell me, Why Kruscal+DFS doesn't work? I have TLE#12.
Should I write Prim?

New tests were added. 40 authors lost AC.

up

I also have TLE 12 and write Kruskal and his advanced version with DSU. It doesn't meter.
But when at finding secondcost i stoped finding, if secondcost became equal to firstcost i got AC at Java with 0.2 sec with complexity o(n^3) at worst case :-)

Edited by author 31.07.2010 19:32

"choose the minimal possible set of trans-planet passages so that he could pass from any planet to any other one via those passages"

If you choose 1-3 and 3-4, you can't reach planet 2 from the other planets.

i got WA as well.can anyone tell me?i don't know the mistake

the same mistake..

the same :(

The same.. WA11

Maybe there is something wrong on your UFS(Union Find Set)...

I also got WA 12, but pass this test correctly...

Ops, I forget that weight of an edge can be equal to 0.

Edited by author 30.06.2007 20:00