Poj Solution 1135

http://poj.org/problem?id=1135

import java.util.Scanner;

public class Main

{

 static final int Inf=9999999;

 public static void main(String[] args)

 {

    Scanner in=new Scanner(System.in);

    int cnt=0;

    while(true)

    {

        cnt++;

        int n=in.nextInt();

        int m=in.nextInt();

        if(n==0&&m==0)break;

        int[][] p=new int[n][n];

        for(int i=0;i< n;i++)

            for(int j=0;j< n;j++)

                p[i][j]=Inf;

        for(int i=0;i < m;i++)

        {

            int x=in.nextInt()-1;

            int y=in.nextInt()-1;

            int len=in.nextInt();

            p[x][y]=p[y][x]=len;

        }

        boolean[] bb=new boolean[n];

        bb[0]=true;

        int[] time=new int[n];

        for(int i=0;i< n;i++)

            time[i]=p[0][i];

        time[0]=0;

        for(int i=0;i< n-1;i++)

        {

            int min=Inf,tag=0;

            for(int j=0;j< n;j++)

            {

                if(!bb[j]&&time[j]< min)

                {

                    min=time[j];

                    tag=j;

                }

            }

            bb[tag]=true;

            for(int j=0;j< n;j++)

                if(!bb[j]&&p[tag][j]< Inf&&time[tag]+p[tag][j]< time[j])

                    time[j]=time[tag]+p[tag][j];

        }

        double maxtime=-Inf;

        int pos=-1;

        for(int i=0;i< n;i++)

        {

            if(time[i]>maxtime)

            {

                maxtime=time[i];

                pos=i;

            }

        }

        double max=-Inf,t;

        int pos1=-1,pos2=-1;

        for(int i=0;i< n;i++)

        {

            for(int j=i+1;j< n;j++)

            {

                t=(time[i]+time[j]+p[i][j])/2.0;

                if(p[i][j]< Inf&&t>max)

                {

                    max=t;

                    pos1=i;pos2=j;

                }

            }

        }

        System.out.println("System #"+cnt);

        System.out.print("The last domino falls after ");

        if(maxtime>=max)

            System.out.printf("%.1f seconds, at key domino %d.nn",maxtime,pos+1);

        else System.out.printf("%.1f seconds, between key dominoes %d and %d.nn",max,pos1+1,pos2+1);

    }

 }

}