pku 2253

2009年7月29日 星期三

题目链接：PKU 2253 Frogger

分类：Dijkastra变种

题目分析与算法原型
        其实这题和PKU 1797很像，Dijkastra中将判断语句改成dis[j]=Mini(dis[j],Max(dis[u],map[u][j]))就行了，刚好和1797相反.........（PS：做了N多的最短路径问题，从明天开始要换口味了，继续学习图论的其他经典算法）

Code:

 1#include<stdio.h>
 2#include<math.h>
 3#define len 205
 4#define max 1000000000
 5
 6double pos[len][2],dis[len];
 7int visit[len],n;
 8
 9double cal(int a,int b)
10{
11    double res;
12    res=sqrt((pos[a][0]-pos[b][0])*(pos[a][0]-pos[b][0])+(pos[a][1]-pos[b][1])*(pos[a][1]-pos[b][1]));
13    return res;
14}
15double Max(double a,double b)
16{
17    return a > b ? a : b;
18}
19void Dijkastra(int s, int v)//s为源点，v为终点（若有的话）
20{
21    int i,j;
22    for(i=1;i<=n;i++)
23    {
24        dis[i]=cal(s,i);
25        visit[i]=0;
26    }
27    visit[s]=1;
28    for(i=1;i<n;i++)
29    {
30        double min=max;
31        int u;
32        for(j=1;j<=n;j++)
33            if(visit[j]==0&&dis[j]<min)
34            {
35                u=j;
36                min=dis[j];
37            }
38
39            if(min==max)return;//此语句对于非连通图是必须的，表示当前已经不存在路径了
40            if(u==v)return ;//若题目是求从给定某个点到另一个给定的点之间的最短路径时，加上这句节时
41            visit[u]=1;
42            for(j=1;j<=n;j++)
43                if(visit[j]==0)
44                {
45                    double k=cal(u,j);
46                    if(Max(dis[u],k)<dis[j])
47                        dis[j]=Max(dis[u],k);
48                }
49    }
50}
51int main()
52{
53    int i,ccase=1;;
54    while(scanf("%d",&n)!=EOF&&n)
55    {
56        for(i=1;i<=n;i++)scanf("%lf%lf",&pos[i][0],&pos[i][1]);
57        Dijkastra(1,2);
58        printf("Scenario #%d\n",ccase++);
59        printf("Frog Distance = %.3lf\n\n",dis[2]);
60    
61    }
62    return 1;
63}
64

posted on 2009-07-29 23:18 蜗牛也Coding 阅读(126) 评论(0)  编辑 收藏 引用


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


<2009年7月>
日一二三四五六
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

导航

统计

常用链接

留言簿(8)

随笔档案(78)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜