216 WA !!Plz Help

[sohel_acm]

I am in a great trouble with 216.I am continuously getting WA for this problem,but i can't find where is the error.I tried several critical input.In all cases my program gave correct output.Now plz someone help me.Here is my code

Code: Select all

#include<stdio.h>
#include<math.h>
#include<string.h>
#define M 100

char c[M]={0};
long int as[M],ii,jj,a[M],ans[M];
//static int po=0;
float matrix[M][M],ss,hh,leng[M],min,sum_dist,final_dist[M];

struct point
{
   float x,y;
}p[M];

void dist(int node)
{
   for(ii=1;ii<=node;ii++)
   {
      for(jj=1;jj<=node;jj++)
      {
         matrix[ii][jj]=0.0;
         matrix[ii][jj]=0.0;
      }
   }
   
   for(ii=1;ii<node;ii++)
   {
      for(jj=ii+1;jj<=node;jj++)
      {
         ss=abs(p[ii].x-p[jj].x);
         ss*=ss;
         hh=abs(p[ii].y-p[jj].y);
         hh*=hh;
         matrix[ii][jj]=sqrt(ss+hh);
         matrix[jj][ii]=matrix[ii][jj];
      }
   }
}


int is_solved(int n,int k)
{
   return (k==n);
}

void process(int b)
{
   int t,sum_dist=0.0;
   for(t=1;t<b;t++)
         sum_dist+=leng[t];
   if(min>sum_dist)
   {
      min=sum_dist;
      for(t=1;t<=b;t++)
      {
         final_dist[t]=leng[t]+16.0;
         ans[t]=as[t];
      }
   }
}

int network(int n,int k,int y)
{
   int u=0,g,s;
   if(a[y]!=0)
      return 0;
   leng[k-1]=matrix[as[k-1]][y];
   as[k]=y;
   a[y]=1;
}

int backtrack(int n,int k)
{
   int h,t,y;
   if(is_solved(n,k))
   {
      process(n);
      a[as[k]]=0;
   }
   k++;
   for(t=1;t<=n;t++)
   {      
      y=network(n,k,t);
      if(y!=0)
      {
         backtrack(n,k);
      }
   }
   a[as[k-1]]=0;
   return 0;
}
void output(int g)
{
   int i,l;
   min=0.0;
   for(l=1;l<g;l++)
      min+=final_dist[l];
   for(i=1;i<g;i++)
   {
      printf("Cable requirement to connect (%0.0f,%0.0f)",p[ans[i]].x,p[ans[i]].y);
      printf(" to (%0.0f,%0.0f) ",p[ans[i+1]].x,p[ans[i+1]].y);
      printf("is %0.2f feet.\n",final_dist[i]);
   }
   printf("Number of feet of cable required is %0.2f.\n",min);
}

void main()
{
   long int i,j=0,l,in,k;
   while(scanf("%ld",&in),in)
   {
      for(i=1;i<=in;i++)
      {
         scanf("%f %f",&p[i].x,&p[i].y);
         a[i]=0;
      }
      dist(in);
      j++;
      printf("**********************************************************\n");
      printf("Network #%ld\n",j);
      min=1000000.00;
      for(i=1;i<=in;i++)
      {
         as[1]=i;
         a[i]=1;
         sum_dist=0.0;
         backtrack(in,1);
      }   
      
      output(in);
      
      for(i=1;i<=in;i++)
         a[i]=0;
   }
}




[Shafaet_du]

Try this cases:

Code: Select all

8
100 150
102 23
34 67
32 63
11 25
132 35
54 122
54 23
8
120 15
102 21
34 64
132 16
1 125
13 135
12 162
55 45
0

output:

Code: Select all

**********************************************************
Network #1
Cable requirement to connect (132,35) to (102,23) is 48.31 feet.
Cable requirement to connect (102,23) to (54,23) is 64.00 feet.
Cable requirement to connect (54,23) to (11,25) is 59.05 feet.
Cable requirement to connect (11,25) to (32,63) is 59.42 feet.
Cable requirement to connect (32,63) to (34,67) is 20.47 feet.
Cable requirement to connect (34,67) to (54,122) is 74.52 feet.
Cable requirement to connect (54,122) to (100,150) is 69.85 feet.
Number of feet of cable required is 395.62.
**********************************************************
Network #2
Cable requirement to connect (132,16) to (120,15) is 28.04 feet.
Cable requirement to connect (120,15) to (102,21) is 34.97 feet.
Cable requirement to connect (102,21) to (55,45) is 68.77 feet.
Cable requirement to connect (55,45) to (34,64) is 44.32 feet.
Cable requirement to connect (34,64) to (1,125) is 85.35 feet.
Cable requirement to connect (1,125) to (13,135) is 31.62 feet.
Cable requirement to connect (13,135) to (12,162) is 43.02 feet.
Number of feet of cable required is 336.10.


no need to use eps

[@li_kuet]

I have tried all the test case from the forum but Can't find out the bug
I used bitmask+dp to solve the problem.
please help

Code: Select all

Removed after AC :D :D


[brianfry713]

Input:

Code: Select all

3
8 16
8 11
9 16
0

AC output:

Code: Select all

**********************************************************
Network #1
Cable requirement to connect (8,11) to (8,16) is 21.00 feet.
Cable requirement to connect (8,16) to (9,16) is 17.00 feet.
Number of feet of cable required is 38.00.