链接 :
http://acm.pku.edu.cn/JudgeOnline/problem?id=2253题意 :两个forger 一个froger 要蹦到另外一个froger处 他们的最短距离是这样定义的 : The frog distance (humans also call it minimax distance) between two stones therefore is defined as the minimum necessary jump range over all possible paths between the two stones.
即为 :两个石头之间的frog distance就是在这两个石头之间的所有路径中最大跳(necessary jump range)最小的。 (以上引自
aowarmen's blog)
想法 :我们通常的dj方法的最短路径是进行边的松弛,判断条件为 d[i] > d[w] + map[w][i] 即对边的松弛,根据三角不等式,
更新后为 d[i] = d[w] + map[w][i];而这个“最短路径”通过的路径里面的最大值,只是判断条件和更新变一下。
即 d[j] > (d[w] > map[w][i] ? d[w] : map[w][i])
更新为选择点的最短距离d[w]和(u, v)的距离里面最大的那个,进行更新.
即 d[i] = d[w] > map[w][i] ? d[w] : map[w][i];
ps : 看discuss里面有用最小生成树做的,而且
aowarmen是用参数搜索做出来的,同样0ms,想不通 + ym中。。。请各位知道的。
或者有更好的方法的, 能提示一下。
代码如下 :
1 #include <stdio.h>
2 #include <string.h>
3 #include <math.h>
4 #define max 201
5 int m, n;
6 double map[max][max], p[max][2];
7 void dj(){
8 int i, j, w, s[max];double d[max], min;
9 memset(s, 0, sizeof(s));
10 for(i = 0; i < m; i++)d[i] = -1;
11 s[0] = 1;d[0] = 0;
12 for(i = 0; i < m; i++)
13 if(map[0][i])d[i] = map[0][i];
14 while(1){
15 w = -1;
16 for(i = 0; i < m; i++)
17 if(!s[i] && d[i] >= 0)
18 if(w == -1 || d[i] < min){
19 min = d[i];
20 w = i;
21 }
22 if(w == -1)break;
23 s[w] = 1;
24 for(i = 0; i < m; i++){
25 if(map[w][i]){
26 if(d[i] > (d[w] > map[w][i] ? d[w] : map[w][i])){
27 d[i] = d[w] > map[w][i] ? d[w] : map[w][i];
28 }
29 }
30 }
31 }
32 printf("Frog Distance = %.3lf\n", d[1]);
33 }
34 int main(){
35 freopen("2253.in","r",stdin);
36 freopen("2253.out","w",stdout);
37 int i, j, c = 1;
38 while(scanf("%d", &m), m){
39 printf("Scenario #%d\n", c++);
40 memset(map, 0, sizeof(map));
41 for(i = 0; i < m; i++)
42 scanf("%lf%lf", &p[i][0], &p[i][1]);
43 for(i = 0; i < m; i++)
44 for(j = i + 1; j < m; j++)
45 map[i][j] = map[j][i] = sqrt((p[j][0] - p[i][0]) * (p[j][0] - p[i][0]) + (p[j][1] - p[i][1]) * (p[j][1] - p[i][1]));
46 dj();puts("");
47 }
48 return 0;
49 }
50
51