传送门：http://www.usaco.org/index.php?page=viewproblem2&cpid=106

这道题还真是完全没思路，真的不知道怎么做，但是看了题解后恍然大悟。

貌似这种与坐标有关的图论题经常拆点耶，把每个点拆成5个点，分别是它本身以及其四联通块。显然，最短路就要过这几个点。然后暴力枚举每对那N*5个点，比如说这两个点是i与j，坐标分别为(xi, yi)与(xj, yj)，该怎么从i走到j呢？要么是(xi, yi)->(xj, yi)->(yi, yj)，要么就是(xi, yi)->(xi, yj)->(xj, yj)，只有这两种走法，可以把这看成（理解成）一种“基本操作”，则任意两点间的最短路必然是几次“基本操作”后的结果！如果这两种走法的路径上都有原始的N个点，则i不能通过这种基本操作到j，否则把它们之间的距离设置为它们的曼哈顿距离。

预处理完之后，就是跑最短路啦。注意这里不要使用Floyd，会T，最好做N次Dijkstra。

程序实现上还有一些小细节，仔细想想就能想通，比如不能以原始的N个点作为中间点来松弛（不然这条路上就有障碍啦）。

代码就不上了，我是用Floyd跑的，T掉了，懒得重写了（我才不会说我们学校清理电脑把我的全部东西都删了呢= =）。

最新文章

1. 【Android端APP 安装包检查】安装包检查具体内容及实现方法
2. 【Selenium】3.介绍Selenium IDE
3. [转]Jquery Ajax用法
4. 2013 Multi-University Training Contest 4 Who's Aunt Zhang
5. 【转】C/C++求模求余运算符——2013-08-20
6. 读《CSCW的一种建模与实现方法》
7. OPC客户端的进程安全初始化
8. emoji图像转码解码 存入数据库
9. Element ui表格展示多张图片问题
10. linux分析apache日志获取最多访问的前10个IP
11. UiPath实践经验总结(一)
12. 循环语句（for，while，do……while），方法概述
13. react中Redux应用框架学习
14. winddow10下 virtualBox Ubuntu网络设置
15. Ubuntu 安装mono
16. Hadoop学习之路
17. firebug,chrome调试工具的使用
18. HttpClient 基于连接池的使用
19. Jenkins自动化CI CD流水线之5--pipeline
20. Appium python Uiautomator2 多进程问题

热门文章

1. Java实现网页截屏
2. iphone5s 耳机更换插头 EarPods change jack
3. 【stl学习笔记】红黑树
4. php monolog 的写日志到unix domain socket 测试终于成功
5. linux用户列表
6. 【原创】PHP扩展开发入门
7. 【Mongodb教程 第一课 补加课1 】windows7 下安装mongodb 开启关闭服务
8. Eclipse导入项目： No projects are found to import
9. 关于 equals()与hashcode()方法
10. 嵌入式开发之davinci--- 8168 电源调试总结