pb91b4.java

designing an automated software installation topology for your company

import java.io.*;

public class pb91b4
{
  public static void main(String args[]) throws IOException
  {
    BufferedReader br=new BufferedReader(new FileReader(new File(args[0])));
    String line="",pointData="";
    int pointNum=0,lineNum=0,a=0,b=0,abTime=0,min=0,minPoint=0,sum=0;
    String pData[]=new String[3];
    boolean flag=false;

    while(true)
    {
      line=br.readLine().trim();
      if (line.equals("0")) break;

      pointNum=Integer.parseInt(line);	//point number
      int pointTable[][]=new int[pointNum][pointNum];

//set max value to array

      for (int i=0;i<pointNum;i++)
      {
        for (int j=0;j<pointNum;j++)
        {
           if (i==j) pointTable[i][j]=0;
           else pointTable[i][j]=300000;
        }
      }


      lineNum=Integer.parseInt(br.readLine().trim());	//line number
      for (int i=0;i<lineNum;i++)
      {
        pointData=br.readLine().trim();
        pData=pointData.split(" ",-1);
        a=Integer.parseInt(pData[0])-1;		//point a
        b=Integer.parseInt(pData[1])-1;		//point b
        abTime=Integer.parseInt(pData[2]);	//time

        pointTable[a][b]=abTime;		//a->b : use Time
        pointTable[b][a]=abTime;		//b->a : use Time
      }

      flag=true;

      while(flag)
      {
        flag=false;
        for (int i=0;i<pointNum;i++)
          for (int j=0;j<pointNum;j++)
            for (int k=0;k<pointNum;k++)
              if ((pointTable[i][k]+pointTable[k][j])<pointTable[i][j])
              {
                pointTable[i][j]=pointTable[i][k]+pointTable[k][j];
                flag=true;
              }
      }

      min=500000;
      for (int i=0;i<pointNum;i++)
      {
        sum=0;
        for (int j=0;j<pointNum;j++) sum+=pointTable[i][j];

        if (sum<min)
        {
          min=sum;
          minPoint=i;
        }
      }

      if (((double)min/(double)pointNum)==(min/pointNum))
        System.out.println((minPoint+1)+":"+(min/pointNum));
      else
      {
        int x=min,y=pointNum,z=0;
        while (y>0)
        {
          x%=y; z=y; y=x; x=z;
        }

        System.out.println((minPoint+1)+":"+(min/x)+"/"+(pointNum/x));
      }
    }
  }
}