1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| #include <cstdio>
#include <queue>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long LL;
const int INF = 1009999999;
int getint() {
int r = 0, k = 1; char c = getchar();
for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
return r * k;
}
struct edge_type {
int to, next, w;
} edge[900005];
typedef pair<int, int> pii;
priority_queue<pii, vector<pii>, greater<pii> > Q;
int cnte, dis[200005], h[200005], n;
bool vis[200005];
void ins(int x, int y, int z) {
edge[++cnte].to = y;
edge[cnte].next = h[x];
edge[cnte].w = z;
h[x] = cnte;
edge[++cnte].to = x;
edge[cnte].next = h[y];
edge[cnte].w = z;
h[y] = cnte;
}
int dijkstra() {
for (int i = 2; i <= n; ++i) dis[i] = INF;
Q.push(make_pair(0, 1)); int now;
while (!Q.empty()) {
now = Q.top().second;
Q.pop();
if (vis[now]) continue;
vis[now] = true;
for (int i = h[now]; i; i = edge[i].next) {
if (vis[edge[i].to]) continue;
if (dis[edge[i].to] > dis[now] + edge[i].w) {
dis[edge[i].to] = dis[now] + edge[i].w;
Q.push(make_pair(dis[edge[i].to], edge[i].to));
}
}
}
return dis[n];
}
int X[200005], Y[200005], id[200005];
int dist(int i, int j) {
return min(abs(X[i] - X[j]), abs(Y[i] - Y[j]));
}
bool cmpX(int x, int y) {
return X[x] < X[y];
}
bool cmpY(int x, int y) {
return Y[x] < Y[y];
}
int main() {
n = getint();
for (int i = 1; i <= n; ++i) {
X[i] = getint(); Y[i] = getint();
id[i] = i;
}
sort(id+1, id+n+1, cmpX);
for (int i = 1; i < n; ++i)
ins(id[i], id[i+1], dist(id[i], id[i+1]));
sort(id+1, id+n+1, cmpY);
for (int i = 1; i < n; ++i)
ins(id[i], id[i+1], dist(id[i], id[i+1]));
printf("%d", dijkstra());
return 0;
}
|
SPFA巨慢。。。