POJ 2253 Frogger（Floyd）

Posted on | In | 阅读

利用Floyd的更新策略，只不过把要更新的值类型从最短路变成最大跨度。输出用%lf WA死我了，改用%f或cout就好了。

C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#define MAX 202

using namespace std;

struct node{
	double x;
	double y;
}stones[MAX];

double arr[MAX][MAX];

int main(){

	int num;
	int ca = 1;
	while(~scanf("%d", &num) && num != 0){
		for(int i = 0; i < num; i++){
			scanf("%lf%lf", &stones[i].x, &stones[i].y);
		}
		for(int i = 0; i < num; i++){
            arr[i][i] = 0;
			for(int j = i+1; j < num; j++){
				arr[i][j] = arr[j][i] = sqrt((stones[i].x - stones[j].x)*(stones[i].x - stones[j].x) + (stones[i].y - stones[j].y)*(stones[i].y - stones[j].y));
			}
		}
		for(int k = 0; k < num; k++){
			for(int i = 0; i < num; i++){
				for(int j = 0; j < num; j++){
					arr[i][j] = min(arr[i][j], max(arr[i][k], arr[k][j]));
				}
			}
		}
		printf("Scenario #%d\n", ca++);
		printf("Frog Distance = %.3f\n\n", (arr[0][1]));
	}
    return 0;
}