cumcm 2000b.cpp

#include "stdio.h" #include "math.h" #include "malloc.h" #include "string.h" #define m 6 #defin

/* * * * * * * * * * * * * * * * * * * * * * * * * * 
*              FLOYD ALGORITHEM                    *                  
*                VERSION 1.0                       *
*             Written By Shen Hui                  *
* * * * * * * * * * * * * * * * * * * * * * * * * */                                                 
/*输入N个字符型数据，并以ENTER结束*/
/*然后输入边表信息，下标从零开始*/
#include "stdio.h"
#include "malloc.h"
#define TRUE 1
#define n 39
#define max 5000
typedef struct
{
  char p[n];
  double w[n][n];
}graph;

graph *ga2;
int visit[n];
int path[n][n];
double C[n][n];
double A[n][n];

graph *creatd(graph *ga)
{
  int i,j;
  ga=(graph*)malloc(sizeof(graph));
  for(i=0;i<n;i++)
    for(j=0;j<n;j++)
      ga->w[i][j]=0;
  ga->w[0][7]=202;         
  ga->w[0][18]=20;          
  ga->w[0][30]=3.1;          
  ga->w[1][7]=1200;         
  ga->w[2][8]=690;           
  ga->w[3][10]=690;          
  ga->w[4][17]=462;          
  ga->w[5][14]=70;           
  ga->w[5][37]=11;          
  ga->w[6][15]=30 ;           
  
  ga->w[6][38]=2;             
  ga->w[7][8]=720;          
  ga->w[7][31]=1.2;         
  ga->w[8][9]=520;          
  ga->w[8][32]=4.2;         
  ga->w[9][10]=170;        
  ga->w[9][33]=7;          
  ga->w[10][11]=160;       
  ga->w[10][17]=88;        
  ga->w[11][12]=70;        
 
  ga->w[11][13]=320;          
  ga->w[12][35]=1;            
  ga->w[13][14]=160;
  ga->w[13][36]=6.2;
  ga->w[14][15]=290;
  ga->w[14][37]=3;
  ga->w[15][38]=2;
  ga->w[16][22]=80;
  ga->w[16][26]=0.2;
  ga->w[17][34]=1;
  
  ga->w[18][19]=195;
  ga->w[18][30]=1;
  ga->w[19][20]=306;
  ga->w[19][29]=0.5;
  ga->w[20][28]=1;
  ga->w[21][22]=1150;
  ga->w[21][27]=60;
  ga->w[22][23]=450;
  ga->w[23][25]=0.3;
  ga->w[24][25]=10.4;
  
  ga->w[25][26]=30.1;
  ga->w[26][27]=75;
  ga->w[27][28]=60.6;
  ga->w[28][29]=19.4;
  ga->w[29][30]=20.5;
  ga->w[30][31]=20.1;
  ga->w[31][32]=68;
  ga->w[32][33]=48;
  ga->w[33][34]=30;
  ga->w[34][35]=22;
  
  ga->w[35][36]=21;
  ga->w[36][37]=42;
  ga->w[37][38]=50;

 for(i=0;i<n;i++)
	 for(j=0;j<n;j++)
		 if(ga->w[i][j]!=0)
			 ga->w[j][i]=ga->w[i][j];
  return(ga);
}

 
double FixRailwayFee(double y)
{
	int x=int(y);
	double r;
	if(x>=300)
		r=20;
	if((x>=301)&&(x<=350))
		r=23;
	if((x>=351)&&(x<=400))
		r=26;
	if((x>=401)&&(x<=450))
		r=29;
	if((x>=501)&&(x<=600))
		r=37;
	if((x>=601)&&(x<=700))
		r=44;
	if((x>=701)&&(x<=800))
		r=50;
	if((x>=801)&&(x<=900))
		r=55;
	if((x>=901)&&(x<=1000))
		r=60;
	if((x>=1001)&&((x%100)==0))
		r=60+((x-1000)%100)*5;
		else r=60+((x-1000)%100)*5+5;
    return r;
}






void transplant(double C[n][n],graph *ga2)
{
 int i,j;
 for(i=0;i<n;i++)
  for(j=0;j<n;j++)
   {
    if((ga2->w[i][j]==0)&&(i==j)) C[i][j]=0;
      else if(ga2->w[i][j]==0) C[i][j]=max;
	   else  C[i][j]=ga2->w[i][j];}
}

  

void FLOYD(double C[n][n],double A[n][n])
{
 int i,j,k,next;
 for(i=0;i<n;i++)
  for(j=0;j<n;j++)
   {
    if(C[i][j]!=max) path[i][j]=j+1; 
     else path[i][j]=0;
    A[i][j]=C[i][j];
   }
 for(k=0;k<n;k++)
  for(i=0;i<n;i++)
   for(j=0;j<n;j++)
    if(A[i][j]>A[i][k]+A[k][j])    
     {
      A[i][j]=A[i][k]+A[k][j];
     if(j>=24) A[i][j]=FixRailwayFee(A[i][j]);    //j=24 is the bound between road and railway
	  path[i][j]=path[i][k];
     }
 
 for(i=0;i<7;i++)
 {
  for(j=0;j<n;j++)
   {
    printf("%5.2f",A[i][j]);
    next=path[i][j];
    if(next==0)
     printf("   %d to %d no path    ",i+1,j+1);
    else
     {
      printf("  %d",i+1);
      while(next!=(j+1))                  /*n*/
       {
	printf("-->%d",next);             /*n*/
	next=path[next-1][j];             /*n*/
       }
      printf("-->%2d\n",j+1);
     }
   }
  printf("\n");
 }
}

void main()
{                   
  ga2=creatd(ga2);
  transplant(C,ga2);
  FLOYD(C,A);
}