1.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS11
* Problem: 534 - Frogger
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=475
* @author Mitterreiter Christian
* @author Posselt Christian
* @version 1.0, 04/24/2011
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.700
*/

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();
int count = 1;

while (n > 0) {

double[][] in = new double[1000][1000];
int[] x = new int[300];
int[] y = new int[300];

//Werte einlesen
for (int i = 0; i < n; i++) {
x[i] = sc.nextInt();
y[i] = sc.nextInt();
}

//Abstände berechnen
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
in[i][j] = in[j][i] = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
}
}

for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
in[i][j] = Math.min(in[i][j], Math.max(in[i][k], in[k][j])); // min-max-distance
}
}
}

//Ergebnisausgabe
System.out.printf("Scenario #%d\n", count++);
System.out.printf("Frog Distance = %.3f\n", Math.sqrt(in[0][1]));

n = sc.nextInt();
System.out.printf("\n");
}
}

------------------------------------------------
}


1.

/**
* FWP, Ausgewhlte Probleme aus dem ACM Programming Contest, WS10/11
* Problem: 534 Frogger
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=475
*
* @author Fabian Liebl
* @version 1.0, 10/06/2010
*
* Method : Floyd-Warshall
* Status : Accepted
* Runtime: 0.420
*/

import java.util.Scanner;

public class Main {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

int tc = 1;
int stones = sc.nextInt();
int[] x,y;
double d;
double[][] dist;

while (stones != 0) {
x = new int[stones];
y = new int[stones];
for (int i = 0; i < stones; i++) {
x[i] = sc.nextInt();
y[i] = sc.nextInt();
}
dist = new double[stones][stones];
for (int i = 0; i < stones; i++) {
for (int j = i + 1; j < stones; j++) {
// Distance between stone i and j
d = Math.sqrt((x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j]));
dist[i][j] = d;
dist[j][i] = d;
}
}

// Warshall-Algorithm
for (int k = 0; k < stones; k++) {
for (int i = 0; i < stones; i++) {
for (int j = 0; j < stones; j++) {
dist[i][j] = Math.min(dist[i][j], Math.max(dist[i][k], dist[k][j]));
}
}
}

System.out.printf("Scenario #%d\nFrog Distance = %.3f\n\n", tc, dist[0][1]);

stones = sc.nextInt();
tc++;
}
}

}



2.



/**
* FWP, Ausgew¤hlte Probleme aus dem ACM Programming Contest, WS10/11
* Problem: 534 - Frogger
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=53
*
* @author Philippe Brousse
* @version 1.0, 10/27/2010
*
* Method : Floyd-Warshall
* Status : Accepted
* Runtime: 0.320
*/
package frogger;

import java.io.IOException;
import java.util.Scanner;

/**
*
* @author Philippe Brousse
*/
public class Main
{

//x- und y-Koordinaten der Steine
private static int[] x_stone;
private static int[] y_stone;
//Pfadl¤ngen von i nach j
private static double[][] pathLengths;

/**
* @param Kommandozeilenargumente werden ignoriert
*/
public static void main(String[] args) throws IOException
{
Scanner input = new Scanner(System.in);

int caseNumber = 0;
do
{
caseNumber++;

//#Stones
int stones = Integer.parseInt(input.next());
if (stones == 0)
//Eingabeende erreicht: 0
{
input.close();
return;
}

//Pfadl¤ngen
pathLengths = new double[stones][stones];
//x,y Koordinaten aller Steine
x_stone = new int[stones];
y_stone = new int[stones];
//bef¼llen
for (int i = 0; i < stones; i++)
{
//Koordinaten f¼r Stein i speichern
x_stone[i] = Integer.parseInt(input.next());
y_stone[i] = Integer.parseInt(input.next());
}

fill(stones);

getLengths(stones);

System.out.println("Scenario #" + caseNumber);
System.out.printf("Frog Distance = %.3f%n%n", pathLengths[0][1]);

}
while (input.hasNext());
}

/**
* Berechne Abstand von i zu j
* @param i Startstein
* @param j Zielstein
* @return distanz
*/
private static double edgeCost(int i, int j)
{
int x = x_stone[i] - x_stone[j];
int y = y_stone[i] - y_stone[j];
return Math.sqrt((x * x) + (y * y));
}

private static void fill(int stones)
{
for (int i = 0; i < stones; i++)
{
for (int j = 0; j < stones; j++)
{
//Pfadl¤ngen speichern
pathLengths[i][j] = edgeCost(i, j);

}
}
}

private static void getLengths(int stones)
{
for (int k = 0; k < stones; k++)
{
for (int i = 0; i < stones; i++)
{
for (int j = 0; j < stones; j++)
{
double oldPath = pathLengths[i][j];
double newPath = Math.max(pathLengths[i][k], pathLengths[k][j]);
//Speichere neuen, k¼rzeren Pfad
pathLengths[i][j] = Math.min(oldPath, newPath);

}
}
}
}
}


3.

package problemSetVolumes.volume005;

import java.util.*;

/**
* FWP, Ausgewhlte Probleme aus dem ACM Programming Contest, SS10
* Problem: 534 - Frogger
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=475
*
* @author Siegfried Ippisch
* @author Michael Haus
* @author Martin Lambeck
* @version 1.0
*
* Method : Floyd–Warshall algorithm
* Status : Accepted
* Runtime: 0.424
*/
public class Frogger {

static Scanner in = new Scanner(System.in);
static List<Point> points = new ArrayList<Point>(200);
static int tcase = 1;

public static void main(String[] args){

while(testcase());
in.close();
}

public static boolean testcase()
{
int nodes = in.nextInt();
double[][] adja = new double[nodes][nodes];

if (nodes == 0)
return false;

points.clear();

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

for (int i = 0; i < nodes; i++)
{
for (int h = 0; h < nodes; h++)
{
adja[i][h] = points.get(i).distance(points.get(h));
}
}

for (int k = 0; k < nodes; k++)
for (int i = 0; i < nodes; i++)
for (int j = 0; j < nodes; j++)
adja[i][j] = Math.min(adja[i][j], Math.max(adja[i][k], adja[k][j]));

System.out.printf("Scenario #%d\nFrog Distance = %.3f\n\n", tcase, adja[0][1]);

//in.nextLine();

tcase++;
return true;
}

}

class Point
{
int x;
int y;

public Point (int xx, int yy)
{
x = xx;
y = yy;
}

public double distance (Point other)
{
int dx = x - other.x;
int dy = y - other.y;

return Math.sqrt(dx * dx + dy * dy);
}
}