1.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS09
* Problem: 534 Frogger
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=475
*
* @author Christoph Hausmann
* @version 0.1, 12/20/2009
*
* Method : Floyd��Warshall algorithm
* Status : Accepted
* Runtime: 0.436
*/

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;


public class Frogger_534 {

public static void main(String... args) {
final Scanner scanner = new Scanner(System.in);

for(int testCase = 1; true; testCase++) {
final int numPoints = scanner.nextInt();

final List<Point> points = new ArrayList<Point>();

if(numPoints == 0)
return;

for(int i = 0; i < numPoints; i++) {
points.add(new Point(scanner.nextInt(),scanner.nextInt()));
}


System.out.println("Scenario #" + testCase);
System.out.printf("Frog Distance = %.3f\n", getFrogDistance(points));
System.out.println();
}
}

private static double getFrogDistance(List<Point> points) {
final double[][] distanceMatrix = computeDistanceMatrix(points);
final double[][] floyd = floyd(distanceMatrix);

return floyd[0][1];
}

private static double[][] floyd(double[][] w) {
/*
Algorithmus von Floyd

(1) Für alle i,j : d[i,j] = w[i,j]
(2) Für k = 1 bis n
(3) Für alle Paare i,j
(4) d[i,j] = min (d[i,j],d[i,k] + d[k,j])
*/

final double[][] d = new double[w.length][w.length];

for(int i = 0; i < w.length; i++) {
for(int j = 0; j < w.length; j++) {
d[i][j] = w[i][j];
}
}

for(int k = 0; k < w.length; k++) {
for(int i = 0; i < w.length; i++) {
for(int j = 0; j < w.length; j++) {
d[i][j] = Math.min(d[i][j], Math.max(d[i][k], d[k][j]));
}
}
}

return d;
}

private static double[][] computeDistanceMatrix(List<Point> points) {
final double[][] distances = new double[points.size()][points.size()];

for(int i = 0; i < points.size(); i++) {
for(int j = 0; j < points.size(); j++) {
distances[i][j] = points.get(i).getDistanceTo(points.get(j));
}
}

return distances;
}

public static class Point {
private final int x;
private final int y;

public Point(int x, int y) {
this.x = x;
this.y = y;
}

public double getDistanceTo(final Point other) {
final int a = x-other.x;
final int b = y-other.y;

final double res = Math.sqrt(a*a + b*b);

return res;
}

@Override
public String toString() {
return "Point(" + x + "," + y + ")";
}
}
}