CHEFGAME-WA

I was getting WA for CHEFGAME after implementing Prim as in the editorial.Could somebody tell where am I going wrong?


[1]


  [1]: http://pastebin.com/Pu7Z9bQP

why are you marking same points as visited if one is visited ? They have to be considered separately.

But why they are having the same coordinates aren’t they?
So in the sample below:
1
2 2
0 0
0 0
1 1
Shouldn’t the answer be 2?

@anuraganand
I’ve understood your point.Here is the changed code.It still is getting a WA.


[1]


  [1]: http://www.codechef.com/viewsolution/2285768

@admin help needed in debugging

http://www.codechef.com/viewsolution/2285768

@bugkiller help needed.

@jaskaran_1 : You are marking visited every time the current maximum is smaller than weight at that index
rep(j,0,N)
{if(!disc[j]&&max<d[j])
{max=d[j];
v=j;
disc[v]=1;}
}

whereas you should mark it only when it is the index with overall minimum weight. It should be:
rep(j,0,N)
{if(!disc[j]&&max<d[j])
{max=d[j];
v=j;
}
}
if(max==0)
break;
disc[v]=1;

AC code : http://www.codechef.com/viewsolution/2294232

2 Likes

Thanks a lot man! I was kinda frustated and that is why I was repeating the question.