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