【k题：公主巡游】

【帝国继承人维多利亚公主举行了举世瞩目的成人礼，将要巡视王国的n个城池。所有城池构成一个凸多边形，给定它们的坐标2]，公主所在的王都为1号城池。】

【若要求每个城池仅去一次，求公主完成巡视的最短距离。】

[注：2≤n≤1000］

即使不是第一次见，众人还是牙疼似的抽了一口气。

……什么玩意都是。

连n的最大取值都比之前多一个0。

一千个城池大盛世！

袁天忍不住道：“珑妹，这道真的很邪门，逼不得已我连记忆化搜索都掏出来试了，还是捋不顺逻辑……”

林珑茫然：“什么是记忆化搜索？”

“……你不知道记忆化搜索？”袁天差点咬到舌头，“……哦，对哦，你刚入门。”

……可眼前人的实力真的很难让他记得这一点啊！！！

他定了定神，又问：“那你准备怎么做啊？不用记忆化搜索更不行的啊……” 林珑想了想：“就正常递归吧。从1出发，那只能去2或n。假设到2，下一步只能去3或n；假设到n，下一步只能去n-1或2——”

“……停停停！”袁天震惊打断，险些劈了音，“凭什么每一步只有两种可能？！公主可以往任意一个城池去的啊！”

“可是所有城池围成了凸多边形。”林珑见他迷茫，顿时有点慌，咬了咬唇，犹豫着小声说，“我觉得……要想总距离最短，路径连线就不能有交叉？”

“……”袁天直了眼，半晌才憋出来一句，“你这是……图形性质？数学定理？……怎么证啊？”

他撞撞邱博：“你能证吗？”

邱博一贯的沉默不怎么说话，闻言摇摇头。袁天还在现场百度这个不知道是怎么回事的性质，林珑已经按这个思