The Captain 题解

20200216题目题解

这是一篇题解祭题解记，但一共就一道题目。（ROS菜大了）

题目如下：

The Captain

给定平面上的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
2

Time limit
20000 ms

Memory limit
262144 kB

OS
Linux

Source
AMPPZ2014

先分析这道题，说实话一开始没什么头绪。第一反应是把两点之间都建一条边，单只建边复杂度就是n²了。（一共建n*（n-1）/2条边）然后看一下n的范围：2<=n<=200000。那n²最大=4e10,1s的话可以大概进行3e7此操作，20s也就6e8次操作，所以必定fake做法，pass。

那么我们来对这道题进行深入思考，看分块是“最短路，最小生成树”那就肯定类似dijkstra求单源最短路径的做法，所以第一感觉是直接直接取路径中所有最短边然后广度优先搜索即可，后来发现此举行不通。

于是想到可以将横纵坐标分别临近（或相同）的两边进行连边，这样的话可以得知有可能使得到达最终点的路径变得更短（最坏的情况也不过是路径相同而已，路径一定不会变得更长）

那么我们现在就分析一下上段所说的话：上段所说的话的意思概括来说就是说从A点到C点，如果中间有B点可途径，那么途径B点便一定是更优的方案；即使不能够使所经路程更短，也一定不会更长。（算法精髓）

好的现在算法思路明确了，那么开始看代码：

 1 #include<bits/stdc++.h>
 2 #define N 400001
 3 #define inf 1000000001
 4 using namespace std;
 5 bool vis[N];
 6 int dis[N];
 7 int head[N];
 8 int n,tot;
 9 priority_queue < pair<int,int> > q;
10 inline void do_it(){
11     for(int i=1;i<=n;i++){
12         dis[i]=inf;
13     }
14     return ;
15 }
16 struct node{
17     int x;
18     int y;
19     int id;
20 }a[N];
21 struct edge{
22     int to;
23     int nxt;
24     int val;
25 }e[2*N];
26 bool cmx(node x,node y){
27     return x.x<y.x;
28 }
29 bool cmy(node x,node y){
30     return x.y<y.y;
31 }
32 void add(int x,int y,int z){
33     e[++tot].to=y;
34     e[tot].nxt=head[x];
35     head[x]=tot;
36     e[tot].val=z;
37     return;
38 }
39 void Dijkstra()
40 {
41     q.push(make_pair(0,1)); memset(vis,0,sizeof(vis)); /*memset(dis,0x3f,sizeof(dis));*/ dis[1] = 0;
42     while(!q.empty())
43     {
44         int x = q.top().second; q.pop(); if(vis[x]) continue; vis[x] = 1;
45         for(int i=head[x];i;i=e[i].nxt)
46         {
47             int to1=e[i].to;
48             if(dis[to1] > dis[x] + e[i].val)
49                 dis[to1] = dis[x] + e[i].val , q.push(make_pair(-dis[to1],to1));
50         }
51     }
52     return ;
53 }
54 int main(){
55     scanf("%d",&n);
56     do_it();
57     for(int i=1;i<=n;i++){
58         scanf("%d%d",&a[i].x,&a[i].y);
59         a[i].id=i;
60     }
61     sort(a+1,a+1+n,cmx);
62     for(int i=1;i<=n-1;i++){
63         int u=a[i].id,v=a[i+1].id;
64         add(u,v,a[i+1].x-a[i].x);
65         add(v,u,a[i+1].x-a[i].x);
66     }
67     sort(a+1,a+1+n,cmy);
68     for(int i=1;i<=n-1;i++){
69         int u=a[i].id,v=a[i+1].id;
70         add(u,v,a[i+1].y-a[i].y);
71         add(v,u,a[i+1].y-a[i].y);
72     }
73     Dijkstra();
74     printf("%d",dis[n]);
75     return 0;
76 }

THE END.