MemoryGarden's Blog

努力 -----------大能猫

C++博客 首页 新随笔 联系 聚合 管理
  118 Posts :: 11 Stories :: 20 Comments :: 0 Trackbacks
链接 :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, 0sizeof(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, 0sizeof(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 





posted on 2008-09-04 22:07 memorygarden 阅读(1115) 评论(2)  编辑 收藏 引用 所属分类: 报告

Feedback

# re: poj 2253 Frogger[未登录] 2008-10-15 15:04 小马
yM。。。。  回复  更多评论
  

# 这题的意思?可以解释清楚点吗? 2008-11-19 20:24 zjhui
这题的意思?可以解释清楚点吗?  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理