ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1982. Electrification Plan

If you have WA #9
Posted by Smilodon_am [Obninsk INPE] 6 Nov 2013 11:26
First I used Kruskal algo but got WA9 verdict.
My program didn't give right answer for next test:
4 1
4
0    1    1    100000
1    0    1    100000
1    1    0    100000
100000    100000    100000    0
100002

Implementation of Prim algo gave the correct answer at last.
Re: If you have WA #9
Posted by Arseniy 7 Feb 2014 22:48
HM, i have right output on this test, but  WA 9
Re: If you have WA #9
Posted by bosenok 19 Jun 2014 04:17
c[i][j] = c[j][i]
This is wrong test
Re: If you have WA #9
Posted by SquidBoy 21 Sep 2015 04:38
This test helped me....

5 2
1 3
0 1 2 3 4
1 0 2 3 4
2 2 0 3 4
3 3 3 0 4
4 4 4 4 0

=8

(I was getting 9).  Basically my algorithm (roughly Prim's) tried to short-cut checking vertex weights.  For any node, make sure you check verices to ALL nodes....
Arseniy wrote 7 February 2014 22:48
HM, i have right output on this test, but  WA 9
Re: If you have WA #9
Posted by lrdx 27 Oct 2015 20:10
Some tests:
4 2
1 4
0 4 8 9
4 0 2 7
8 2 0 1
9 7 1 0

4 2
1 3
0 6 7 8
6 0 2 3
7 2 0 4
8 3 4 0

Edited by author 27.10.2015 20:10
Re: If you have WA #9
Posted by Booster 19 Feb 2019 12:07
5 3
1 3 2
0 1 2 3 4
1 0 2 3 4
2 2 0 3 4
3 3 3 0 4
4 4 4 4 0

Edited by author 19.02.2019 12:09
Re: If you have WA #9
Posted by Hristo Nikolaev (B&W) 27 Mar 2023 17:15
One more test that helped me to find my error for WA #9.

5 2
1 5
0 1 100 150 200
1 0 10 50 200
100 10 0 11 100
150 50 11 0 2
200 200 100 2 0