2016huasacm暑假集训训练三 B-Frogger

时间:2021-04-27 09:15:13

题目链接: https://vjudge.net/contest/123674#problem/B

题意:一只青蛙在湖中一颗石头上, 它想去有另一只青蛙的石头上,但是 湖里的水很脏,它不愿意游泳,所以它要跳过去;

给出 两只青蛙所在石头的坐标, 及 湖里其他石头的坐标;任一两个坐标点间都是双向连通的。显然从A到B存在至少一条的通路,每一条通路的元素都是这条通路中前后两个点的距离,这些距离中又有一个最大距离。

现在要求求出所有通路的最大距离,并把这些最大距离作比较,把最小的一个最大距离作为青蛙的最小跳远距离。

只能说英语是硬伤,刚开始一直没看懂题目,最后还是一懂半懂,以为直接直接排序输出最大值就行,直接wa,后来还是用了floyd算法才Ac

 import java.io.BufferedInputStream;
import java.util.Scanner; public class Main {
static int n;
static int cases = 0;
static int stone[][];
static double map[][];
public static void main(String[] args) {
Scanner s = new Scanner(new BufferedInputStream(System.in));
while (s.hasNext()) {
cases++;
n = s.nextInt();
if (n == 0) {
return;
}
stone = new int[n][2];
map = new double[n][n];
for (int i = 0; i < n; i++) {
stone[i][0] = s.nextInt();
stone[i][1] = s.nextInt();
} for (int i = 0; i < n; i++) { //i j 之间边的长度
for (int j = 0; j < n; j++) {
map[i][j] = Math.sqrt((stone[i][0] - stone[j][0]) * (stone[i][0] - stone[j][0])
+ (stone[i][1] - stone[j][1]) * (stone[i][1] - stone[j][1]));
}
} System.out.println("Scenario #" + cases); System.out.printf("Frog Distance = %.3f\n\n", floyd());
}
s.close();
} static double floyd() {
for (int i = 0; i < n; i++) {
for (int k = 0; k < n; k++) {
for (int j = 0; j < n; j++) { if (map[k][i] != 0 && map[i][j] != 0
&& map[k][j] > (map[k][i] > map[i][j] ? map[k][i] : map[i][j])) {
map[k][j] = (map[k][i] > map[i][j] ? map[k][i] : map[i][j]);
}
}
}
}
return map[0][1];
}
}