1046 Shortest Distance
2024-10-21 15:29:54
题意:给出一个环和结点之间的距离,求任意两结点之间的最近距离。如图:
思路:令数组dis[i]表示1号结点逆时针至i号结点的距离,初始化dis[1]=0,其他值在输入是确定,即
dis[i] | 0 | 1 | 3 | 7 | 21 |
i | 1 | 2 | 3 | 4 | 5 |
这样,起点start和终点end之间逆时针方向的距离即为 d=abs(dis[end]-dis[start]) ,注意要加绝对值,不然,比如起点4到终点2的距离是dis[2]-dis[4]=-6,就为负了。同时用total记录环的总距离,起点start和终点end之间逆时针方向的距离即为 total-d 。对于任意两结点u,v之间的最短距离,就是其顺时针和逆时针距离最较小值。
代码:
#include <cstdio> #include <cstdlib> #define MIN(x,y) (x)<(y)?(x):(y) ; }; int main() { ;//total表示总的距离 scanf("%d",&n); ;i<=n;i++){ scanf("%d",&d); total+=d; dis[i+]=d+dis[i]; } int m,s,e; scanf("%d",&m); ;i<m;i++){ scanf("%d%d",&s,&e); d=abs(dis[e]-dis[s]); printf("%d\n",MIN(d,total-d)); } return 0; }
最新文章
- 火星坐标、百度坐标、WGS-84坐标相互转换及墨卡托投影坐标转经纬度JavaScript版
- 【2016-10-27】【坚持学习】【Day14】【GlobalAssemblyInfo 】
- iOS开发拓展篇—静态库
- 流媒体基础实践之——Nginx-RTMP-module 指令详解
- MongoDB - MongoDB CRUD Operations
- grunt + compass retina sprites
- Android源代码之Gallery专题研究(1)
- 关于 const 成员函数
- Linux常用命令大全(2)
- 伸展树(Splay树)的简要操作
- 前端面试题整理—JavaScript篇(二)
- [原创]K8Cscan插件之C段旁站扫描\子域名扫描
- nginx buffered to a temporary 解决
- matlab : Nelder mead simplex 单纯形直接搜索算法;
- VS Code 管理 .NET Core解决方案
- MyBatis 与 Hibernate 到底哪个更快?
- Java_8排序(冒泡排序和选择排序)
- Java关键字instanceof
- Packet Tracer 5.0实验(一) 交换机的Telnet远程登录设置
- 如何在CentOS 7上使用vsftpd设置ftp服务器
热门文章
- 文件IO大纲
- yii2:多条件多where条件下碰到between时,between语句如何处理呢?
- Prism技术开发文档(五星级)
- mysql中的过滤分组
- 18-THREE.JS 基本材质
- JavaScript高级程序设计读后感(一)
- 解决webpack vue 项目打包生成的文件,资源文件均404问题
- NLTK下载语言素材中碰到的certificate verify failed (_ssl.c:749)
- Leetcode 1018. Binary Prefix Divisible By 5
- Photon Cloud Networking: OnPhotonSerializeView Not Firing