# 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);

}

}

}
```
This entry was posted in poj. Bookmark the permalink.