【题解】洛谷P1027 Car的旅行路线

题目

洛谷P1027 Car的旅行路线

题解

此题要求最短路。题中的机场代表点,但有部分点的坐标没有给出,需要运用几何知识求出。此题的存点方式有一定技巧,序号为i的城市的机场下标为4*i,4*i+1,4*i+2,4*i+3,这样可以将城市与机场的编号关联起来。

代码

Subscribe
提醒
guest
1 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年8月18日 下午7:54

【小白解析】
此题大体不难理解,相比上一个dijkstra算法题来说并不晦涩。
此题的数据存放方式如题解部分中所说:

序号为i的城市的机场下标为4*i,4*i+1,4*i+2,4*i+3,这样可以将城市与机场的编号关联起来

需要一定的位运算技巧,但本质上十分简单粗暴。第63行为数据储存的具体实现,其中:
4*i==i<<2
4*i+1==i<<2+1==i<<2|1
4*i+2==i<<2+2==i<<2|2
第23行中的4*i+3也由相同方法实现。其本质是将i所有位向左移动两位,空出的两个位用于存放00,01,10,11这四个机场信息;最左端的i自然成为城市信息的提示符。
64行的get_place()函数并不难理解,本质上是找出给定三个点所连成的三段中最长的线段,即为矩形对角线;再根据矩形ABCD四顶点中,Ax+Cx==Bx+Dx,Ay+Cy==By+Dy的性质,求出第四个点。此为基本的初中数学知识,当然在座各位可能幼儿园时就有所耳闻了。
随后进入耳熟能详的dijkstra()算法,其基本套路继承前一章的精髓。第47行的get_price()方法体现了最初i<<2的必要性:第31行中,a>>2正是为了查看原先被右移的i——即城市编号。若所求线路两端处于同一城市内,其路费则与该城市高速收费有关;若在不同城市,则交给飞机费用处理。
程序每通过a城市的一个机场检索出到达任何点的费用(d[y]表示到达y机场的最少费用),就将到达b城市的四个机场费用检索一遍取最小值。a城的四个机场都遍历完后,得到的ans即是最小值。