POJ 2253 C++ (图论)

//前几天的题,别人都用floyd_warshall,我就用dijkstra;
//而这个题很多人都用dijkstra,我就用floyd_warshall;
//两个字,flody的代码敲起来就是简单,但效率比较的低,复杂度是(n^3)

#include<iostream>
#include<cmath>
#include <algorithm>
using namespace std;
int main()
{ int n,Case,i,j,k;
  int x[201],y[201];
  int map[201][201];
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  Case=1;
  while(scanf("%d",&n),n!=0)
       {    memset(map,0,sizeof(map));
            for(i=1;i<=n;i++)
              scanf("%d%d",&x[i],&y[i]);
             for( i=1;i<=n;i++)
               for( j=i+1;j<=n;j++)
                   { map[i][j]=abs((x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i]));
                     map[j][i]=map[i][j];
                    }
          for( k=1;k<=n;k++)
              for( i=1;i<=n;i++)
                  for( j=i+1;j<=n;j++)
                      { if(map[i][k] && map[k][j] && map[i][k]<map[i][j] && map[k][j]<map[i][j])
                           { if(map[i][k]>map[k][j])
                                map[i][j]=map[i][k];
                             else
                                map[i][j]=map[k][j];
                           }  
                        
                            map[j][i]=map[i][j];
                       }          
        printf("Scenario #%d\n",Case++);
        printf("Frog Distance = %.3lf\n\n",sqrt(map[1][2]*1.0));
   }
  
   return 0;
}    

posted on 2008-11-27 00:17 蜗牛 阅读(1408) 评论(0)  编辑 收藏 引用 所属分类: ACM ICPC


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


<2008年11月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
30123456

导航

统计

常用链接

留言簿(1)

随笔分类(20)

随笔档案(20)

Favorites

搜索

最新评论

阅读排行榜

评论排行榜