【BZOJ】【4152】【AMPZZ2014】The Captain

最短路

　　题解：http://zyfzyf.is-programmer.com/posts/97953.html

　　按x坐标排序，相邻点之间连边。满足dist(x1,x3)<=dist(x1,x2)+dist(x2,x3)（因为可以走y）

　　再按y坐标排序，相邻点之间连边。同上

　　然而SPFA挂了……写了Dijkstra

 1 /**************************************************************
 2     Problem: 4152
 3     User: Tunix
 4     Language: C++
 5     Result: Accepted
 6     Time:4304 ms
 7     Memory:27204 kb
 8 ****************************************************************/
 9  
10 //BZOJ 4152
11 #include<vector>
12 #include<queue>
13 #include<cstdio>
14 #include<cstring>
15 #include<cstdlib>
16 #include<iostream>
17 #include<algorithm>
18 #define rep(i,n) for(int i=0;i<n;++i)
19 #define F(i,j,n) for(int i=j;i<=n;++i)
20 #define D(i,j,n) for(int i=j;i>=n;--i)
21 using namespace std;
22 typedef long long LL;
23 inline int getint(){
24     int r=1,v=0; char ch=getchar();
25     for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-1;
26     for(; isdigit(ch);ch=getchar()) v=v*10-'0'+ch;
27     return r*v;
28 }
29 const int N=2e5+10,INF=~0u>>1;
30 /*******************template********************/
31  
32 int head[N],to[N<<3],nxt[N<<3],l[N<<3],cnt;
33 void add(int x,int y,int z){
34     to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; l[cnt]=z;
35     to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; l[cnt]=z;
36 }
37 int n,d[N];
38 struct node{
39     int x,y,num;
40 }a[N];
41 bool cmpx(node a,node b){return a.x<b.x;}
42 bool cmpy(node a,node b){return a.y<b.y;}
43 typedef pair<int,int> pii;
44 #define mp make_pair
45 #define se second
46 priority_queue<pii,vector<pii>,greater<pii> >Q;
47 bool vis[N];
48 int main(){
49 #ifndef ONLINE_JUDGE
50     freopen("4152.in","r",stdin);
51     freopen("4152.out","w",stdout);
52 #endif 
53     n=getint();
54     F(i,1,n) a[i].x=getint(),a[i].y=getint(),a[i].num=i;
55     sort(a+1,a+n+1,cmpx);
56     F(i,1,n-1) add(a[i].num,a[i+1].num,a[i+1].x-a[i].x);
57     sort(a+1,a+n+1,cmpy);
58     F(i,1,n-1) add(a[i].num,a[i+1].num,a[i+1].y-a[i].y);
59  
60     F(i,2,n) d[i]=INF;
61     d[1]=0;
62     Q.push(mp(0,1));
63     while(!Q.empty()){
64         int x=Q.top().se; Q.pop();
65         if (vis[x]) continue;
66         vis[x]=1;
67         for(int i=head[x];i;i=nxt[i])
68             if (d[to[i]]>d[x]+l[i]){
69                 d[to[i]]=d[x]+l[i];
70                 Q.push(mp(d[to[i]],to[i]));
71             }
72     }
73     printf("%d
",d[n]);
74     return 0;
75 }

View Code

4152: [AMPPZ2014]The Captain

Time Limit: 20 Sec Memory Limit: 256 MB
Submit: 141 Solved: 62
[Submit][Status][Discuss]

Description

给定平面上的n个点，定义(x1,y1)到(x2,y2)的费用为min(|x1-x2|,|y1-y2|)，求从1号点走到n号点的最小费用。

Input

第一行包含一个正整数n(2<=n<=200000)，表示点数。

接下来n行，每行包含两个整数x[i],y[i](0<=x[i],y[i]<=10^9)，依次表示每个点的坐标。

Output

一个整数，即最小费用。

Sample Input

5
2 2
1 1
4 5
7 1
6 7

Sample Output

HINT

Source

鸣谢Claris上传

[Submit][Status][Discuss]