我要啦免费统计
http://acm.pku.edu.cn/JudgeOnline/problem?id=2253


#include
<iostream>
#include
<cmath>
using namespace std;

#define MAXN 1002
#define inf 1000000000
typedef 
double elem_t;
elem_t mat[MAXN][MAXN];
elem_t dist[MAXN];
int num[MAXN][2];

double distance(int a1,int a2,int b1,int b2)
{
       
return sqrt((double)((a1-b1)*(a1-b1)+(a2-b2)*(a2-b2)));
}

void dijkstra(int n,int s)
{
    
int v[MAXN],i,j;
    
int k;
    
for (i=0;i<n;i++)
        dist[i]
=mat[s][i],v[i]=0;//初始化
    
    
for (dist[s]=0,j=0;j<n;j++){

        
for (k=-1,i=0;i<n;i++)//估计计距离最小的顶点k
            if (!v[i]&&(k==-1||dist[i] < dist[k]))
                k
=i;

        
for (v[k]=1,i=0;i<n;i++)
            
if (!v[i] && mat[k][i]>0.0)//&& max(dist[k],mat[k][i]) > dist[i])
                {
                     dist[i] 
= min( max(dist[k],mat[k][i]),dist[i]);
                     
                  
//dist[i]=min(dist[k],mat[k][i]);
               }


    }

}


int main()
{
    
    
int n,m,k,x1,y1;
    
    
    
    
for(int i = 1;;i ++){
      scanf(
"%d",&n);
      
if( n == 0)break;
       memset(mat,
0,sizeof(mat));
       
forint j=0;j<n;j++)
         scanf(
"%d %d",&num[j][0],&num[j][1]);
       
forint k=0;k<n;k++)
         
forint j=0;j<n;j++){
            mat[k][j]
=distance(num[k][0],num[k][1],num[j][0],num[j][1]);     
         }


       

       dijkstra(n,
0);

       printf(
"Scenario #%d\n",i);
       printf(
"Frog Distance = %0.3lf\n\n",dist[1]);//dist[n-1]<<endl<<endl;
    }


    
return 0;
}


/*
1
3 3
1 2 3
1 3 4
2 3 5

*/

posted on 2008-11-06 21:55 阅读(1817) 评论(6)  编辑 收藏 引用 所属分类: pku

评论:
# re: pku 2253 Frogger 2008-11-06 22:51 | Wang Feng
acm中如果涉及到图的算法,可否直接使用boost graph library?  回复  更多评论
  
# re: pku 2253 Frogger[未登录] 2008-11-07 23:34 | cdy20
一般自己写,不用库的。
库的灵活性不会好
而且主要还是运行时间的问题
有些题目,用类库的很容易超时。@Wang Feng
  回复  更多评论
  
# re: pku 2253 Frogger 2009-03-29 10:56 | 12342
你好,请问
for (v[k]=1,i=0;i<n;i++)
if (!v[i] && mat[k][i]>0.0)//&& max(dist[k],mat[k][i]) > dist[i])
{
dist[i] = min( max(dist[k],mat[k][i]),dist[i]);

//dist[i]=min(dist[k],mat[k][i]);
}
这是什么意思啊,这几步的详细作用是什么?谢谢,麻烦解释一下!
  回复  更多评论
  
# re: pku 2253 Frogger[未登录] 2009-03-29 22:15 | cdy20
@12342
这是最基本的更新的
d[i]表示源点到点i的路径距离,这里取它最小的数
min( max(dist[k],mat[k][i]),dist[i]);
其中max(dist[k],mat[k][i])这一句表示每次跳,选择的步子最长的
min表示最短路的,有点dp的思想 min(d[i])
每次更新d[i]
。。。。。
好好看题目的。“
To execute a given sequence of jumps, a frog's jump range obviously must be at least as long as the longest jump occuring in the sequence.
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.


  回复  更多评论
  
# re: pku 2253 Frogger[未登录] 2009-03-29 22:18 | cdy20
这只froger每次跳的时候找邻近可以跳的石头,找那个些尽可能距离远的

然后总体结果路径要想最短的
  回复  更多评论
  
# re: pku 2253 Frogger 2009-03-30 13:51 | 12342
又去看了看dijkstra,终于明白了!谢谢啊!!!  回复  更多评论
  

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