1342:【例4-1】最短路径问题

简介: 1342:【例4-1】最短路径问题

1342:【例4-1】最短路径问题

时间限制: 1000 ms         内存限制: 65536 KB

【题目描述】

平面上有n个点(n<=100),每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。

若有连线,则表示可从一个点到达另一个点,即两点间有通路,通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。

【输入】

共n+m+3行,其中:

第一行为整数n。

第2行到第n+1行(共n行) ,每行两个整数x和y,描述了一个点的坐标。

第n+2行为一个整数m,表示图中连线的个数。

此后的m 行,每行描述一条连线,由两个整数i和j组成,表示第i个点和第j个点之间有连线。

最后一行:两个整数s和t,分别表示源点和目标点。

【输出】

一行,一个实数(保留两位小数),表示从s到t的最短路径长度。

【输入样例】

5

0 0

2 0

2 2

0 2

3 1

5

1 2

1 3

1 4

2 5

3 5

1 5

【输出样例】

3.41

1. #include <bits/stdc++.h>
2. using namespace std;
3. int zb[105][2];
4. double dist[105][105]; 
5. int n,m,a,b,s,t;
6. void Floyd(){//搜索路径
7.  for(int k=1;k<=n;k++)
8.    for(int i=1;i<=n;i++)
9.      for(int j=1;j<=n;j++)
10.         if((i!=j)&&(i!=k)&&(j!=k)&&(dist[i][j]>dist[i][k]+dist[k][j]))
11.           dist[i][j]=dist[i][k]+dist[k][j];
12. }
13. int main() {
14.     cin>>n;
15. for(int i=1;i<=n;i++)cin>>zb[i][0]>>zb[i][1];
16.     cin>>m; 
17. memset(dist,0x7f,sizeof(dist));
18. for(int i=1;i<=m;i++){
19.     cin>>a>>b;
20.     dist[a][b]=dist[b][a]=sqrt((zb[a][0]-zb[b][0])*(zb[a][0]-zb[b][0])+(zb[a][1]-zb[b][1])*(zb[a][1]-zb[b][1]));
21.   }
22.   cin>>s>>t;
23.   Floyd();
24. printf("%.2lf",dist[s][t]);
25. return 0;
26. }


相关文章
|
运维 负载均衡 网络协议
linux网络管理(链路聚合、桥接网络、故障排查、常用工具)
网卡的链路聚合就是将多块网卡连接起来,当一块网卡损坏,网络依旧可以正常运行,可以有效的防止因为网卡损坏带来的损失,同时也可以提高网络访问速度。
1537 0
linux网络管理(链路聚合、桥接网络、故障排查、常用工具)
|
Linux
Linux VXLAN小实验
该文介绍了如何在两台运行CentOS 7的Linux主机(T620和T630)之间建立VXLAN隧道。通过配置VXLAN ID、远程和本地IP,以及设置隧道接口和路由,实现10.0.10.12和10.0.10.13之间的通信。文中提供了详细的配置命令,并展示了成功ping通和抓包的验证结果。
193 4
|
10月前
|
机器学习/深度学习 监控 数据可视化
企业上网监控:Kibana 在网络监控数据可视化
在网络监控中,Kibana 作为一款强大的数据可视化工具,与 Elasticsearch 配合使用,可处理大量日志数据,提供丰富的可视化组件,帮助企业高效管理网络活动,保障信息安全。通过索引模式和数据映射,Kibana 能够组织和分类原始数据,支持深入分析和异常检测,助力企业识别潜在安全威胁。
191 5
|
人工智能 文字识别 算法
通义语音AI技术问题之个人声音定制应用对于用户声音的复刻如何解决
通义语音AI技术问题之个人声音定制应用对于用户声音的复刻如何解决
174 4
|
iOS开发 MacOS
CocoaPods安装失败解决方法
CocoaPods安装失败解决方法
241 2
|
Linux 编译器 网络安全
linux 交叉编译libcurl库
linux 交叉编译libcurl库
687 1
|
Kubernetes Cloud Native 微服务
作者推荐|剖析云原生服务框架中服务发现机制的核心原理与实现机制
作者推荐|剖析云原生服务框架中服务发现机制的核心原理与实现机制
475 0