最短路径问题

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

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

小提示:

  1. 两点的距离:如果点\(A\)坐标为\((x_A,y_A)\),点\(B\)的坐标为\((x_B,y_B)\)\(dis(A,B) = \sqrt{ (x_A-x_B)^2+(y_A-y_B)^2}\)
    C++中求根使用sqrt();
  2. 保留两位小数:使用double变量,double ans;print("%.2lf",ans);

输入

共n+m+3行。

  • 第 1 行:整数n

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

  • 第n+2行为一个整数m,\(m \leq 1000\),表示图中连线的个数。

  • 此后的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



#include <bits/stdc++.h>
using namespace std;
int a,b,n,m,vis[10010],x[10010],y[10010];
double dis[10010];
bool d[1100][1100];
queue<int> q;
void bfs()
{
	q.push(a);
	dis[a]=0;
	vis[a]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=1;
		for(int i=1;i<=b;i++)
		{
			if(d[u][i]&&!vis[i])
			{
				q.push(i);
				dis[i]=dis[u]+sqrt(double(x[i]-x[u])*double(x[i]-x[u])+double(y[i]-y[u])*double(y[i]-y[u]));
				vis[i]=1;
				if(i==b)
				{
					cout << fixed << setprecision(2) << dis[i];
					return;
				}
			}
		}
	}
}
int main()
{
	cin >> n;
	for(int i=1;i<=n;i++)
	{
		cin >> x[i] >> y[i];
	}
	cin >> m;
	for(int i=1;i<=m;i++)
	{
		int f,ff;
		cin >> f >> ff;
		d[f][ff]=d[ff][f]=1;
	}
	cin >> a >> b;
	bfs();
	return 0;
}

原文链接:https://www.cnblogs.com/momotrace/p/shortest-road_pr.html

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:最短路径问题 - Python技术站

(0)
上一篇 2023年4月24日
下一篇 2023年4月24日

相关文章

  • 红与黑

    有一个矩形房间,覆盖正方形瓷砖。每块瓷砖涂成了红色或黑色。一名男子站在黑色的瓷砖上,由此出发,可以移到四个相邻瓷砖之一,但他不能移动到红砖上,只能移动到黑砖上。编写一个程序,计算他通过重复上述移动所能经过的黑砖数(一开始站立的黑砖也要算)。 输入 开头行包含两个正整数W和H,W和H分别表示矩形房间的列数和行数,且都不超过20.每个数据集有H行,其中每行包含W…

    C 2023年4月24日
    00
  • STL 容器 002 (vector 详解)

    为什么 各方面表现都比较中等, 适用范围广 尾插很快, 查找也比较快 是什么 动态数组 特点: 动态数组, 三个指针控制 两倍增长 扩充的方法: 不能原地扩充, 因为后面可能会有其他的东西, 必须在 其他地方开辟一块更大的内存 提供[] 所有的有连续空间的容器都有[] iterator是class类型的 怎么样 制造 两倍增长 //push_back() 检…

    C++ 2023年4月18日
    00
  • MordernC++之左值(引用)与右值(引用)

    左值与右值 C++中左值与右值的概念是从C中继承而来,一种简单的定义是左值能够出现再表达式的左边或者右边,而右值只能出现在表达式的右边。 int a = 5; // a是左值,5是右值 int b = a; // b是左值,a也是左值 int c = a + b; // c是左值,a + b是右值 另一种区分左值和右值的方法是:有名字、能取地址的值是左值,没…

    C++ 2023年4月17日
    00
  • XMake学习笔记(1):Windows(MSYS2)下MinGW-w64环境搭建和XMake安装

    以前写的C++基本都是C with STL,大多是面向过程的算法题,或者比较小的项目,然后经常报各种编译错误(对编译原理不熟),经常把人搞到崩溃,搞不懂构建、链接之类的东西。 现在开始记录一下XMake的学习笔记,记录一些学习过程中踩的坑,在这篇文章,你将学习到Windows下利用MSYS2进行Mingw-w64环境搭建和XMake安装,并用Xmake构建一…

    C++ 2023年4月30日
    00
  • Linux/Ubuntu系统下使用VS Code配置C/C++开发环境

        在Ubuntu下,使用VS Code来编辑代码或进行开发非常方便,下面记录一下如何配置gcc/g++编译器和GDB调试工具。 准备工作: 1. 安装VS Code,过程略。 2. 为VS Code安装C/C++ Extension Pack 扩展组件,其他插件会附带安装 3. Ubuntu系统自带g++和gdb,查看一下 配置环境: VS Code …

    C++ 2023年5月7日
    00
  • 用C++编写一个简单的发布者和订阅者

    摘要:节点(Node)是通过 ROS 图进行通信的可执行进程。 本文分享自华为云社区《编写一个简单的发布者和订阅者》,作者: MAVER1CK 。 @[toc] 参考官方文档:Writing a simple publisher and subscriber (C++) 背景 节点(Node)是通过 ROS 图进行通信的可执行进程。 在本教程中,节点将通过话…

    C++ 2023年4月27日
    00
  • L1-087 机工士姆斯塔迪奥*(使用C++动态数组new暴力实现)

    L1-087 机工士姆斯塔迪奥 分数 20 全屏浏览题目 切换布局 作者 DAI, Longao单位 杭州百腾教育科技有限公司在 MMORPG《最终幻想14》的副本“乐欲之所瓯博讷修道院”里,BOSS 机工士姆斯塔迪奥将会接受玩家的挑战。 你需要处理这个副本其中的一个机制:N×M 大小的地图被拆分为了 N×M 个 1×1 的格子,BOSS 会选择若干行或/及…

    C++ 2023年4月18日
    00
  • 【Visual Leak Detector】核心源码剖析(VLD 1.0)

    说明 使用 VLD 内存泄漏检测工具辅助开发时整理的学习笔记。本篇对 VLD 1.0 源码做内存泄漏检测的思路进行剖析。同系列文章目录可见 《内存泄漏检测工具》目录 目录 说明 1. 源码获取 2. 源码文件概览 3. 源码剖析 3.1 注册自定义 AllocHook 函数 3.2 存储调用堆栈信息 3.3 生成泄漏检测报告 4. 其他问题 4.1 如何区分…

    C++ 2023年4月27日
    00
合作推广
合作推广
分享本页
返回顶部