http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=1867

 #include<stdio.h>
#include<string.h>
#include<math.h>
const int maxn = ;
const int INF=<<;
double dis[maxn][maxn];
struct node
{
double x;
double y;
} f[maxn];//储存每个点的坐标
int n,m;
void init()
{
for (int i = ; i <= n; i ++)
{
for (int j = ; j <= n; j ++)
{
dis[i][j] = INF;
}
dis[i][i] = ;
}
}
void floyd()
{
int i,j,k;
for (k = ; k <= n; k ++)
{
for (i = ; i <= n; i ++)
{
for (j = ; j <= n; j ++)
{
if(dis[i][j] > dis[i][k] + dis[k][j])//更新距离
dis[i][j] = dis[i][k] + dis[k][j];
}
}
}
}
int main()
{
scanf("%d",&n);
init();
for (int i = ; i <= n; i ++)
{
scanf("%lf%lf",&f[i].x,&f[i].y);
}
scanf("%d",&m);
int u,v;
while(m--)
{
scanf("%d%d",&u,&v);
double d = sqrt((f[u].x-f[v].x)*(f[u].x-f[v].x)+(f[u].y-f[v].y)*(f[u].y-f[v].y));//计算u、v 之间的距离
if (dis[u][v] > d) // 判断重边
{
dis[u][v] = d;
dis[v][u] = d;
}
}
int s,e;
scanf("%d%d",&s,&e);
floyd();
printf("%.2f\n",dis[s][e]);
return ;
}

最新文章

  1. 24章 创建TPL自定义模板(1)
  2. js-高级技术
  3. VMware安装虚拟系统问题
  4. Sql Server2005恢复备份数据库问题-Error:3154 3219
  5. C/C++易错点
  6. UIBezierPath
  7. AS3.0下去除flash右键菜单
  8. 获取机器网卡的物理(MAC)地址
  9. S7-200以太网通信
  10. python数据结构之堆(heap)
  11. 一个小误区 JS中的contains
  12. Office_PPT_让你一分钟完成上百张图片的快速保存
  13. 第三个Sprint冲刺第4天
  14. Jenkins-job迁移
  15. mysql二进制日志详解
  16. InfoPath读取List到重复表
  17. 全局 SqlConnection
  18. js随笔记录
  19. 使用 xhprof 进行 php 的性能分析
  20. django导入/导出原始数据

热门文章

  1. python PIL相关操作
  2. (转)Arcgis for Js之Graphiclayer扩展详解
  3. seam remote 返回的map结构
  4. privot函数使用
  5. picturebox中添加图片
  6. centos安装指定mysql
  7. Bequeath Connection and SYS Logon
  8. Cat VS Dog HDU_3829(最大独立集最大匹配)
  9. 【7】Django网页视图模板处理
  10. Codeforces 919C - Seat Arrangements