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就不会超时了。
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就不会超时了。
const int kMaxN = 100005, kINF = 0x3f;int n;typedef struct P{ int x, y;};typedef struct Node{ int value; int id; bool operator <(const Node & t)const { return value < t.value; }};Node X[kMaxN], Y[kMaxN];P points[kMaxN];int dist[kMaxN];int used[kMaxN];vector<vector<int>> path(kMaxN);inline int GetLength(int a, int b){ return min(abs(points[a].x - points[b].x), abs(points[a].y - points[b].y));}int Spfa(){ used[1] = 1; memset(dist, kINF, sizeof(dist)); dist[1] = 0; queue<int> Q; Q.push(1); while (!Q.empty()) { int u = Q.front(); Q.pop(); used[u] = 0; for (int i = 0; i < path[u].size(); i++) { int v = path[u][i]; if (dist[u] + GetLength(u, v) < dist[v]) { dist[v] = dist[u] + GetLength(u, v); if (used[v] == 0) { Q.push(v); used[v] = 1; } } } } return dist[n];}int main(){ scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d %d", &points[i].x, &points[i].y); X[i].value = points[i].x; X[i].id = i; Y[i].value = points[i].y; Y[i].id = i; } sort(X + 1, X + n + 1); sort(Y + 1, Y + n + 1); for (int i = 2; i <= n; i++) { path[X[i].id].push_back(X[i - 1].id); path[X[i - 1].id].push_back(X[i].id); } for (int i = 2; i <= n; i++) { path[Y[i].id].push_back(Y[i - 1].id); path[Y[i - 1].id].push_back(Y[i].id); } printf("%d\n", Spfa()); return 0;
}
Read full article from hihoCoder 1138-Islands Travel | bitJoy > code