#include "iostream.h"
#include<stdio.h>
#include<conio.h>


#define  M   17
#define  M1  53
#define  large 10000
#define  NN  150000
#define MAX 10000.0

float d[M1][M1];
unsigned char P[M1][M1][15];
int num[M1][M1];


float simple(float **a)
{int k1 ,k2;
float r,r1,rr=0;
	for(k1=0;k1<M;k1++)
	{r=a[k1][0];	
		for(k2=1;k2<M;k2++)
		if(a[k1][k2]<r)r=a[k1][k2];
		if(r!=large)
		{rr=rr+r;
		for(k2=0;k2<M;k2++)
		if(a[k1][k2]!=large)a[k1][k2]-=r;
		}
	}
    for(k1=0;k1<M;k1++)
	{r1=a[0][k1];	
		for(k2=1;k2<M;k2++)
		if(a[k2][k1]<r1)r1=a[k2][k1];
		if(r1!=large)
		{rr=rr+r1;
		for(k2=0;k2<M;k2++)
		if(a[k2][k1]!=large)a[k2][k1]-=r1;
		}
	}
return rr;
}

long int *use(float **a)
{ int k1 ,k2,r1,c1,r=0,c=0;
  float  l1[M],l2[M],l=-1;
  long int *p,p1[2];
 for(k1=0;k1<M;k1++)
 { l1[k1]=a[k1][0];r1=-1;
	 for(k2=0;k2<M;k2++)
	 if(a[k1][k2]==0) 		 
		 if(r1==-1) r1=0;
		else     {l1[k1]=0;break;}
	 else if(a[k1][k2]<l1[k1])
			{l1[k1]=a[k1][k2];}
  }
 for(k2=0;k2<M;k2++)
 {l2[k2]=a[0][k2];c1=-1;
    for(k1=0;k1<M;k1++)
		if(a[k1][k2]==0)
			if(c1==-1)c1=0;
			else      {l2[k2]=0;break;}
	     else if(a[k1][k2]<l2[k2])
		 {l2[k2]=a[k1][k2];}
 }
for(k1=0;k1<M;k1++)
    for(k2=0;k2<M;k2++)
	if(a[k1][k2]==0&&(l1[k1]+l2[k2]>l))
	{r=k1;c=k2;l=l1[k1]+l2[k2];}
 p1[0]=r;p1[1]=c;
 p=p1;
 return p;
}

void main()
{FILE *pp=fopen("E:\\共享資料庫\\temp\\distance.doc","r");
 long int i,j,k1,k2,k,E,N,ans,x,*p,k3,k4,k5,y;
 //int  bb[53]={50,38,2,3,39,4,5,6,7,8,40,9,41,10,11,42,12,43,13,14,15,44,45,16,17,18,19,46,20,21,47,48,22,23,24,49,25,26,27,28,51,53,29,52,30,31,32,33,34,35,36,37,1};
 int  gama=0,*cen,*ET1[2],**ET,vv[M][2];
// int	bb[53]={50,38,2,3,39,4,5,6,47,19,45,7,8,40,9,41,10,11,42,12,43,13,14,15,44,16,17,18,46,20,21,48,22,23,24,49,25,26,51,27,28,53,29,52,30,31,32,33,34,35,36,37,1};//
 //int bb[53]={50,38,3,39,4,45,7,8,40,9,41,10,11,42,12,43,13,14,15,44,16,17,18,46,2,5,6,47,19,20,21,48,22,23,24,49,25,26,51,27,28,53,29,52,30,31,32,33,34,35,36,37,1};
 //int	bb[53]={50,38,3,39,4,8,40,9,41,10,42,12,43,14,15,44,16,17,22,23,24,49,26,51,2,5,6,47,19,45,7,11,13,18,46,20,21,48,25,27,28,53,29,52,30,31,32,33,34,35,36,37,1};//
 //int	bb[53]={50,38,2,3,39,4,5,6,47,19,45,7,8,40,9,41,10,11,42,12,43,13,14,15,44,16,17,18,46,20,21,48,22,23,24,49,25,26,51,27,28,53,29,52,30,31,32,33,34,35,36,37,1};//
 int bb[53]={50,38,3,39,4,7,8,40,9,41,10,11,42,12,43,13,14,15,44,16,17,18,46,2,5,6,47,19,45,20,21,48,22,23,24,49,25,26,51,27,28,53,29,52,30,31,32,33,34,35,36,37,1};
// int	bb[53]={50,2,3,39,4,5,6,47,19,45,7,8,40,9,41,10,11,42,12,43,13,14,15,44,16,17,18,46,20,21,48,22,23,24,49,25,26,51,27,28,53,29,52,30,31,32,33,34,35,36,37,38,1};//
//2,3kuai int	bb[53]={50,2,3,39,4,5,6,47,19,45,7,8,40,9,41,10,11,42,12,43,13,14,15,44,16,17,18,46,20,21,48,22,23,24,49,25,50,26,51,27,28,53,29,52,30,31,32,33,34,35,36,37,1};//

 //int bb[53]={50,3,7,27,39,4,5,6,17,53,29,31,8,20,40,9,41,52,30,10,11,42,12,38,2,28,43,13,14,15,44,47,19,16,45,18,46,21,48,22,23,24,49,25,26,51,32,33,34,35,36,37,1};//
long int *parent,*L;
 float *C,*r,U,xia,**A[NN],**A3,**A4,*A1,*A2,r1;
 int v1,v2,dump;
 float dis;
 int n=M1;
 int l,m; 
  C=new float[NN];
  r=new float[NN];
  parent=new long int[NN];
  cen=new  int[NN];
  L=new long int[NN];
  ET1[0]=new   int[NN];
  ET1[1]=new  int[NN];
  ET=ET1;
  
 // ET=new long int*[NN];

for(i=0;i<n;i++)
  for(j=0;j<n;j++)
    {
     if(i==j)  { d[i][j]=0.0;num[i][j]=0; }
     else
	  {
	   d[i][j]=MAX+1.0;
	  }
    }
for(i=0;i<91;i++)
 {
  fscanf(pp,"%c%d,%d,%f%c",&dump,&v1,&v2,&dis,&dump);
  fscanf(pp,"%c%d,%d,%f%c",&dump,&v1,&v2,&dis,&dump);
  d[v1-1][v2-1]=d[v2-1][v1-1]=dis;
  if(d[v1-1][v2-1]<MAX)
      {
      P[v1-1][v2-1][0]=v1;P[v1-1][v2-1][1]=v2;num[v1-1][v2-1]=2;
      P[v2-1][v1-1][0]=v2;P[v2-1][v1-1][1]=v1;num[v2-1][v1-1]=2;
      }
 }
fclose(pp);

for(k=0;k<n;k++)
  for(i=0;i<n;i++)
     for(j=0;j<n;j++)
       if(d[i][k]+d[k][j]<d[i][j])
	  {
	   d[i][j]=d[i][k]+d[k][j];
	   num[i][j]=num[i][k]+num[k][j]-1;
	   for(l=0;l<num[i][k];l++) P[i][j][l]=P[i][k][l];l--;
	   for(m=1;m<num[k][j];m++)  P[i][j][l+m]=P[k][j][m];
	  }
for(i=0;i<n;i++)
 d[i][i]=large;

gama=36;
A3=new float*[M];
for(k1=0;k1<M;k1++)
{ A1=new float[M];
		 for(k2=0;k2<M;k2++)
		 {if(k1!=0)
				if(k2!=0)A1[k2]=d[bb[k1+gama]-1][bb[k2+gama]-1];
				else     A1[k2]=d[bb[k1+gama]-1][bb[k2]-1];
		 else   if(k2!=0)  A1[k2]=d[bb[k1]-1][bb[k2+gama]-1];
				else       A1[k2]=d[bb[k1]-1][bb[k2]-1];  
		 }
	A3[k1]=A1;
}
A[0]=A3;

/*printf("The shortest distance:\n\t");
for(i=48;i<M;i++)  printf("%d\t",i+1); printf("\n");
for(i=0;i<M1;i++)
  {
  printf("%d\t",i+1);
  for(j=0;j<M1;j++) printf("%.1f\t",d[i][j]);
  printf("\n");
  }*/
printf("The shortest distance:\n\t");
for(i=0;i<M;i++)  printf("%d\t",i+1); printf("\n");
for(i=0;i<M;i++)
  {
  printf("%d\t",i+1);
  for(j=0;j<M;j++) printf("%.1f\t",A[0][i][j]);
  printf("\n");
  }
 
r1=simple(A[0]);

 //for(k1=0;k1<M;k1++)
 //parent[k1][0]=-1;
 parent[0]=-1;
 E=0;U=large;
k=0;cen[E]=0;
C[0]=r1;N=0;
ET[0][0]=0;ET[1][0]=0;
 while(C[E]<U)
 {
	 p=use(A[E]);
	 i=p[0];j=p[1];
	 if(i==j) cout<<"good"<<endl;
	 parent[N+1]=E;parent[N+2]=E;
	 ET[0][N+1]=i;ET[1][N+1]=j;
	 ET[0][N+2]=0;ET[1][N+2]=0;
	 if(ET[0][E]!=ET[1][E]||E==0)  {cen[N+1]=cen[E]+1;cen[N+2]=cen[E]+1;}
	 else							{cen[N+1]=cen[E];cen[N+2]=cen[E];}
//	 A[N+1]=copy(A[E]);A[N+2]=copy(A[E]);
	 A4=new float*[M];
	for(k1=0;k1<M;k1++)
	 {
		 A2=new float[M];
		 for(k2=0;k2<M;k2++)
		 {A2[k2]=A[E][k1][k2];}
		 A4[k1]=A2;
	 }
	 A[N+2]=A4;
	 k1=N+1;k2=0;
	vv[k2][0]=ET[0][k1];vv[k2][1]=ET[1][k1];
	while(parent[k1]!=0)
	 {k1=parent[k1];
	  if(ET[0][k1]!=ET[1][k1])
	  {k2++;vv[k2][0]=ET[0][k1];vv[k2][1]=ET[1][k1];}
	 }
		k3=0;y=0;	 
		 for(k1=0;k1<=k2;k1++)
		 {k3=vv[k1][0];k4=vv[k1][1];
		 x=1;
		 while(x) 
		 {for(k5=k1+1;k5<=k2;k5++)
			  if(vv[k5][0]==k4) 
			  {k4=vv[k5][1];break;}
		  if(k5>k2) x=0;
		 }
		 if(k4==k3) y=1;
		 }


	 //if(ET[0][N+1]==0||ET[1][N+1]==0)
	//	 k2++;
	
	if(y==1&&cen[N+1]!=M) L[++k]=-1;
	else
	{
	 A3=new float*[M];
	 	 for(k1=0;k1<M;k1++)
	 {
		 A1=new float[M];
		 for(k2=0;k2<M;k2++)
		 {A1[k2]=A[E][k1][k2];}
		 A3[k1]=A1;
	 }
	 A[N+1]=A3;
    
	 for(k1=0;k1<M;k1++)
	 {	A[N+1][i][k1]=large;
		A[N+1][k1][j]=large;
	 }
	 A[N+1][j][i]=large;
	 r[N+1]=simple(A[N+1]);
	 C[N+1]=C[E]+r[N+1];
	     if(C[N+1]<U)
		 if(cen[N+1]==M)
		 {U=C[N+1];
	     ans=N+1;
		 }
//	     else 
//		 {L[++k]=N+1;}//add 
    L[++k]=N+1;
	}
	for(k1=0;k1<M;k1++)
	{delete []  A[E][k1];}
	 delete []  A[E];
		cout<<k<<",";
	A[N+2][i][j]=large;
    r[N+2]=simple(A[N+2]);
	C[N+2]=C[E]+r[N+2];
//	if(C[N+2]<U){L[++k]=N+2;}//add k=k+1
	L[++k]=N+2;
	N=N+2;
	
	k1=0;
	for(x=1;x<=k;x++)
	{   if(L[x]==-1) k1++;
		else if(C[L[x]]>U)
		{
		for(k1=0;k1<M;k1++)
			{delete [] A[L[x]][k1];}
		delete []  A[L[x]];
		L[x]=-1;
		}
	}
	if(k1!=k)  
	{xia=U+1;
		for(x=1;x<=k;x++)
			if(L[x]!=-1&&C[L[x]]<xia)
			{k1=x;xia=C[L[x]];}
	L[k1]=-1;E=k1;
	}
	else              C[E]=large;
}
//cout<<20.9+8.3+24+15.2+19.1<<endl;
cout<<k<<",";
cout<<"Least cost="<<U<<endl;
while(ans!=-1)
{
if(ET[0][ans]!=ET[1][ans])	//cout<<bb[ET[0][ans]+gama]<<"--"<<bb[ET[1][ans]+gama]<<",";
{
if(ET[0][ans]==0)
	cout<<bb[ET[0][ans]];
else cout<<bb[ET[0][ans]+gama];
cout<<"--";
if(ET[1][ans]==0)cout<<bb[ET[1][ans]];
else              cout<<bb[ET[1][ans]+gama];
cout<<",";
}
ans=parent[ans];
}
//getch();
}