hihoCoder 1138-Islands Travel #1138 : Islands Travel 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 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就不会超时了。 SPFA的介绍可以看我之前的题目。 完整代码如下： [cpp] #include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<cstdlib> #include<queue> #include<cstring> #include<vector> using namespace std; 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; } [/cpp] 本代码提交AC，用时867MS，内存20MB。]]>