spoj.pl/problems/BLINNET/
Tried with all my inputs and is working good .. not able to figure out mistake ..
My approach
node ->i -- Start vertex
node ->j -- End vertex
node ->c -- Cost
Scanning all the edges into a array of Nodes .. Sorting them with Radix sort (Bit wise from LSB for 32 bits)
Optimization - I am not storing edges which are already stored.
I mean
scanf("%d %lld",&j,&co);
if(j>i) -- This statement skips edges connecting from current node to already inputted nodes (j - destination , i - present )
Then using Kruskal's algorithm .. Keeping track of visited nodes with a boolean array and running the loop till i visit n nodes.
#include <cstdio>
class node
{
public:
int i,j;
unsigned int c;
node()
{ }
node (int a,int b,long long d)
{
i=a;
j=b; c=d;
}
};
node arr[1000000],arr2[1000000],arr3[1000000];
int ctr;
bool visited[10020];
void radsort(int len)
{
int m,f1,f2,p=0;
for(long long i=1;p<=32;i=i<<1,p++)
{
f1=0; f2=0;
for(int j=0;j<len;j++)
if(((arr[j].c) & i) == 0 )
arr2[f1++]=arr[j];
else
arr3[f2++]=arr[j];
m=0;
for(int j=0;j<f1;j++)
arr[m++]=arr2[j];
for(int j=0;j<f2;j++)
arr[m++]=arr3[j];
}
}
long long kruks(int n)
{
int i,j,k=-1,cn=0,ii,jj;
long long ans=0;
for(i=0;i<=n;i++)
visited[i]=0;
while(cn<n)
{
k++;
ii=arr[k].i; jj=arr[k].j;
if(visited[ii]==1 && visited[jj]==1)
continue;
if(visited[ii]==0 && visited[jj]==0)
cn++;
visited[ii]=visited[jj]=1;
ans+=arr[k].c;
cn++;
}
return ans;
}
int main()
{
int t,n,p,mr,i,j,k;
long long co;
scanf("%d",&t);
while(t--)
{
ctr=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%*s%d",&p);
while(p--)
{
scanf("%d %lld",&j,&co);
if(j>i)
{
node n(i,j,co);
arr[ctr]=n;
ctr++;
}
}
}
radsort(ctr);
printf("%lld\n",kruks(n));
}
return 0;
}
Thanks 
