耐克店 和 苹果店必须相连

Sample Input
4
2 3
0 0
1 0
0 -1
1 -1
0

Sample Output
3.41

 # include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <cmath>
# define LL long long
using namespace std ; const int INF=0x3f3f3f3f;
const int MAXN=;
bool vis[MAXN];
double lowc[MAXN];
int n ;
double cost[MAXN][MAXN] ; struct poin
{
int x ;
int y ;
}p[MAXN]; double Prim()//点是0~n-1
{
double ans=;
memset(vis,false,sizeof(vis));
vis[]=true;
for(int i=;i<n;i++)lowc[i]=cost[][i];
for(int i=;i<n;i++)
{
double minc=INF;
int p=-;
for(int j=;j<n;j++)
if(!vis[j]&&minc>lowc[j])
{
minc=lowc[j];
p=j;
}
if(minc==INF)return -;//原图不连通
ans+=minc;
vis[p]=true;
for(int j=;j<n;j++)
if(!vis[j]&&lowc[j]>cost[p][j])
lowc[j]=cost[p][j];
}
return ans;
} int main()
{ // freopen("in.txt","r",stdin) ;
while(scanf("%d" , &n) != EOF)
{
if (n == )
break ;
int i , j ;
int pp , qq ;
scanf("%d %d" , &pp , &qq) ;
for (i = ; i < n ; i++)
scanf("%d %d" , &p[i].x , &p[i].y) ;
for (i = ; i < n ; i++)
for (j = i+ ; j < n ; j++)
{
double t = sqrt((double)(p[i].x - p[j].x) * (p[i].x - p[j].x) + (p[i].y - p[j].y) * (p[i].y - p[j].y)) ;
cost[i][j] = t ;
cost[j][i] = t ;
}
double k = cost[pp-][qq-] ;
cost[pp-][qq-] = ;
cost[qq-][pp-] = ;
k += Prim() ;
printf("%.2lf\n" , k) ; }
return ;
}

最新文章

  1. Flex 中画图工具(drawTool)失效
  2. 我的android学习经历9
  3. Python ValueError: IO operation on closed file
  4. Java设计模式——装饰者模式
  5. IoC 依赖注入、以及在Spring中的实现
  6. For Exam (Java常用设计模式) 介绍
  7. Python面向对象编程——引言
  8. Cocoa &amp; Cocoa Touch概念
  9. Ibatis.net防Sql注入
  10. Rotate Array 解答
  11. JFreeChart多坐标轴曲线图
  12. java面试题大全-基础方面
  13. [NOIP2012提高组] CODEVS 1200 同余方程(扩展欧几里德算法)
  14. Mysql ODBC 5.1 Driver免安装脚本
  15. DOM范围
  16. poj2342 Anniversary party
  17. 增加临时表空间组Oracle11g单实例
  18. SSM整合Shiro 身份验证及密码加密简单实现
  19. php 把数字转化为大写中文
  20. Linux启动与禁止SSH用户及IP的登录

热门文章

  1. canvas实现时钟
  2. python -- 异步IO 协程
  3. Tomcat8.5配置https启动报空指针错误
  4. Kettle基本概念学习
  5. change丶未来科技公众号成立了!!!!!!!!!
  6. caffe 中 python 数据层
  7. TCP 链接 存在大量 close_wait 等待
  8. 使用flask_socketio实现服务端向客户端定时推送
  9. C++ vector 使用笔记
  10. mysql外键(FOREIGNKEY)使用介绍