题号:NC234577
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
Special Judge, 64bit IO Format: %lld
题目描述
题目背景
嘤嘤最近在摸鱼。她每天原神只上线20分钟,做一下每日、清一下体力就下号了。(你看,她题面都写的那么简洁,这摸鱼,多是一件美事啊!)
她在摸鱼,所以她渊下宫还没有开始肝,有很多的宝箱、常世之荚、渊海矿髓、珊瑚蝶等物资,她必须全部拿完!
她在摸鱼,所以她想找到一条最短路径将这些物资收集完全!
她在摸鱼,所以这个任务就交给你了!
PS: 爱摸鱼的嘤嘤同学拿着从渊下宫收集的原石在0人池歪了77,嘤嘤气的说起了嘤语:嘤!嘤嘤嘤!嘤嘤嘤嘤嘤嘤!嘤嘤嘤!!嘤嘤嘤!!嘤嘤嘤嘤嘤!
题目描述
首先,我们忽略高度,将渊下宫看成二维地图,嘤嘤的
初始位置为 )
。
嘤嘤知道地图上所有宝箱、常世之荚、渊海矿髓、珊瑚蝶、传送锚点的位置,她可以在初始位置或到达一个宝箱、常世之荚、渊海矿髓或珊瑚蝶的位置时在此位置建立一个口袋锚点。
传送锚点和口袋锚点的作用是:你可以在任意位置传送至任意锚点。(注意:口袋锚点可以同时存在多个,此处与游戏设定不同)
你需要帮助嘤嘤计算出她找完所有物资所需的最短路径。
输入描述:
在第一行中,先输入四个整数
,表示宝箱、常世之荚、渊海矿髓、珊瑚蝶的个数,再输入一个整数
表示传送锚点的位置。
接下来
行,每行两个整数
,表示宝箱的位置。
接下来
行,每行两个整数
,表示常世之荚的位置。
接下来
行,每行两个整数
,表示渊海矿髓的位置。
接下来
行,每行两个整数
,表示珊瑚蝶的位置。
接下来
行,每行两个整数
,表示传送锚点的位置。
数据保证一个位置最多只有一个宝箱、常世之荚、渊海矿髓或珊瑚蝶。
输出描述:
一个实数,表示嘤嘤从初始位置
开始收集完所有物资的最短路径经过的距离。
你的答案与正确答案误差的绝对值不应超过
。
示例1
输入
复制
1 1 1 0 1
2 0
3 0
2 1
1 0
说明
你可以从初始位置(0,0)传送至传送锚点(1,0),然后从(1,0)移动1到达宝箱(2,0),并在(2,0)建立一个口袋锚点,再从(2,0)移动1到达常世之荚(3,0),从(3,0)传送回口袋锚点(2,0),从(2,0)移动1到达渊海矿髓(2,1),所以最短路径为3