hihoCoder 1138-Islands Travel | bitJoy > code

hihoCoder 1138-Islands Travel | bitJoy > code

There are N islands on a planet whose coordinates are (X1, Y1), (X2, Y2), (X3, Y3) ..., (XN, YN). You starts at the 1st island (X1, Y1) and your destination is the n-th island (XN, YN). Travelling between i-th and j-th islands will cost you min{|Xi-Xj|, |Yi-Yj|} (|a| denotes the absolute value of a. min{a, b} denotes the smaller value between a and b) gold coins. You want to know what is the minimum cost to travel from the 1st island to the n-th island.

输入
Line 1: an integer N.

Line 2~N+1: each line contains two integers Xi and Yi.

For 40% data, N<=1000，0<=Xi,Yi<=100000.

For 100% data, N<=100000，0<=Xi,Yi<=1000000000.

输出
Output the minimum cost.

样例输入
3
2 2
1 7
7 6

样例输出
2

---

本题实质上是单源最短路径问题，只是两点间的距离需要自己算。我先后尝试了Dijkstra算法和朴素SPFA算法，都超时，后来参考这篇博客，在SPFA之前需要对数据进行预处理。

原始SPFA时，点(x,y)和其余n-1个点的边都需要尝试，这样计算量就很大，但是因为距离函数是min{|Xi-Xj|, |Yi-Yj|}这样的，和点(x,y)"距离"最近的点(x',y')是那些x'和x最近或者y'和y最近的点。所以点(x,y)实际上只需要尝试4条边，分别是靠近x的前后两个点和靠近y的上下两个点。

所以我们需要对所有点分别按x和y排序，然后重新构造一个图，这个图中，每个点只和另外4个点有边，这样使得图的复杂度大幅下降，再使用SPFA就不会超时了。

Read full article from hihoCoder 1138-Islands Travel | bitJoy > code