正文

图论++【洛谷p1744】特价采购商品&&【一本通1342】最短路径问题

IP云
IP云V管理员/3 阅读
10/01
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

（虽然题面不是很一样，但是其实是一个题qwq）

【传送门】

算法标签：

利用Floyed的o（n3）算法：

（讲白了就是暴算qwq）

从任意一条单边路径开始。所有两点之间的距离是边的权，或者无穷大，如果两点之间没有边相连。
对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。
Floyed算法的话算出的是一个表，通过算法，任意两点间的最短路都会被算出来，时间耗费比较大，容易炸掉

下面代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int n,m,p,q,s,t;
double a[][],dis[][];//a数组代表的是每家店的横纵坐标，dis[i][j]表示从i走到j点的路径长短
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%lf%lf",&a[i][],&a[i][]);//按要求输入横纵坐标
memset(dis,0x7f,sizeof(dis));//把数组初始化为一个很大的数
scanf("%d",&m);
for(int i=;i<=m;i++){
scanf("%d%d",&p,&q);
double x=a[p][]-a[q][],y=a[p][]-a[q][];
dis[q][p]=dis[p][q]=sqrt(x*x+y*y);//利用两点间距离公式求距离
}
for(int k=;k<=n;k++)
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
if((i!=j)&&(i!=k)&&(j!=k)&&(dis[i][j]>dis[i][k]+dis[k][j]))//如果找到一个比直达更短的中间点，更新他
dis[i][j]=dis[i][k]+dis[k][j];
scanf("%d%d",&s,&t);
printf("%.2lf",dis[s][t]);
}

end-

图论++【洛谷p1744】特价采购商品&&【一本通1342】最短路径问题的更多相关文章

  1. 洛谷 P4779【模板】单源最短路径（标准版）

    洛谷 P4779[模板]单源最短路径(标准版) 题目背景 2018 年 7 月 19 日,某位同学在 NOI Day 1 T1 归程 一题里非常熟练地使用了一个广为人知的算法求最短路. 然后呢? 10 ...

  2. 洛谷——P1744 采购特价商品

    P1744 采购特价商品 题目背景 <爱与愁的故事第三弹·shopping>第一章. 题目描述 中山路店山店海,成了购物狂爱与愁大神的“不归之路”.中山路上有n(n<=100)家店, ...

  3. 洛谷 P1744 采购特价商品

    题目背景 <爱与愁的故事第三弹·shopping>第一章. 题目描述 中山路店山店海,成了购物狂爱与愁大神的“不归之路”.中山路上有n(n<=100)家店,每家店的坐标均在-1000 ...

  4. 洛谷P1283 平板涂色 &amp&semi;&amp&semi;一本通1445：平板涂色

    题目描述 CE数码公司开发了一种名为自动涂色机(APM)的产品.它能用预定的颜色给一块由不同尺寸且互不覆盖的矩形构成的平板涂色. 为了涂色,APM需要使用一组刷子.每个刷子涂一种不同的颜色C.APM拿 ...

  5. 洛谷P3371 【模板】单源最短路径

    P3371 [模板]单源最短路径 282通过 1.1K提交 题目提供者HansBug 标签 难度普及/提高- 提交  讨论  题解 最新讨论 不萌也是新,老司机求带 求看,spfa跑模板40分 为什么 ...

  6. &lbrack;洛谷P4779&rsqb;【模板】单源最短路径（标准版）

    题目大意:单元最短路径(卡$SPFA$) 题解:$dijkstra$($\underline{\hspace{0.5em}}\underline{\hspace{0.5em}}gnu\underlin ...

  7. 洛谷 P3371 【模板】单源最短路径 【链式前向星&plus;SPFA】

    题目描述 如题,给出一个有向图,请输出从某一点出发到所有点的最短路径长度. 输入输出格式 输入格式: 第一行包含三个整数N.M.S,分别表示点的个数.有向边的个数.出发点的编号. 接下来M行每行包含三 ...

  8. 洛谷 P3371 【模板】单源最短路径&lpar;堆优化dijkstra&rpar;

    题目描述 如题,给出一个有向图,请输出从某一点出发到所有点的最短路径长度. 输入输出格式 输入格式: 第一行包含三个整数N.M.S,分别表示点的个数.有向边的个数.出发点的编号. 接下来M行每行包含三 ...

  9. 洛谷P3371 【模板】单源最短路径（弱化版）（SPFA解法）

    题目背景 本题测试数据为随机数据,在考试中可能会出现构造数据让SPFA不通过,如有需要请移步 P4779. 题目描述 如题,给出一个有向图,请输出从某一点出发到所有点的最短路径长度. 输入输出格式 输 ...

随机推荐

  1. Android上的事件流操作数据库

    最近在浏览某篇有关事件流的文章时,里面提到了数据的流处理,兴趣来了,就想看看能否在Android端实现一个. 根据文章的介绍,将每次数据的变更事件,像是插入,删除或者更新等,记为一个不可变的事件,让数 ...

  2. POJ 1142 Smith Numbers（史密斯数）

    Description 题目描述 While skimming his phone directory in 1982, Albert Wilansky, a mathematician of Leh ...

  3. Machine Learning for hackers读书笔记&lpar;五&rpar;回归模型：预测网页访问量

    线性回归函数 model<-lm(Weight~Height,data=?) coef(model):得到回归直线的截距 predict(model):预测 residuals(model):残 ...

  4. Receive Windows Messages In Your Custom Delphi Class - NonWindowed Control - AllocateHWnd

    http://delphi.about.com/od/windowsshellapi/a/receive-windows-messages-in-custom-delphi-class-nonwind ...

  5. Packetbeat协议扩展开发教程 一

    原文链接:http://elasticsearch.cn/article/48 Packetbeat(https://www.elastic.co/products/beats/packetbeat) ...

  6. 基于visual Studio2013解决算法导论之008快速排序算法

     题目 快速排序 解决代码及点评 #include <stdio.h> #include <stdlib.h> #include <malloc.h> #in ...

  7. C&num;调用SCL2008 动态库SCL&lowbar;API&lowbar;cdecl&period;dll or SCL&lowbar;API&lowbar;Stdcall&period;dll，提示找不到指定模块

    在公司用的联想 ThinkPad T430i,原装配置及系统,开机巨慢.按下开机键到登陆界面超过1分钟,再到桌面这个时间就难说了,多时有超过3分钟,进入桌面还要等待几分钟才能正常操作.新年过来向公司领 ...

  8. Servlet生命周期和注解配置

    Servlet的生命周期和注解配置问题 /* Servlet? 运行在服务器上的小程序 定义浏览器访问到Tomcat的规则 一.生命周期? 1.创建 2.提供服务 3.被销毁 二.servlet3.0 ...

  9. AngularJS移动端页面input无法输入

    用angularJS写手机页面,有时候会发现input输入框点击了却不能输入,或者长按才能输入,可能是因为input绑定了ng-click导致,可去掉ng-click,将ng-click绑定的方法改用 ...

  10. js中apply详解

    学习http://www.cnblogs.com/delin/archive/2010/06/17/1759695.html 1.对象的继承,一般的做法是复制:Object.extend protot ...