The Captain

文章目录

• The Captain
• • 题目描述
  • 分析
  • 代码

题目描述

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

分析

我们第一时间会想把所有点都连上边,这样在跑一遍dijkstra,不就可以了吗？
但是

对于100%的数据，n<=200000

那我们就想一下如何优化呢
我从样例哪里拿来3个数来看一下

idxy

1	2	2
2	1	1
3	4	5

1到2，需要$min(|X_1-X_2|,|Y_1-Y_2|)=1费用$
1到3，需要$min(|X_1-X_3|,|Y_1-Y_3|)=2费用$
2到3，需要$min(|X_2-X_3|,|Y_2-Y_3|)=3费用$
$1+2=3$难道是巧合？
我们来分析一下

• 如果$|X_1-X_2|$和$|X_1-X_3|$都是最小或最大的话，那么把$X_1$当成中转站$|X_1-X_2|+|X_1-X_3|=|X_2-X_3|$、
• 如果$|X_1-X_2|$和$|X_1-X_3|$是一个大，一个小的话，那么把$X_1$当成中转站$|X_1-X_2|+|X_1-X_3|<|X_2-X_3|$

所以我们可以把$X$排序，相邻存边；在把$Y$排序，相邻存边，一共存$4n$条边
这部分的代码我就不放了，到后面去看吧

代码

有点长

#include<bits/stdc++.h> using namespace std; int n,d[200010]; struct node {int x,y,id; }a[200010]; struct edge {int x,s;bool operator<(const edge&a)const{return s>a.s;} }; bool cmpx(node a,node b) {if(a.x==b.x)return a.y<b.y;return a.x<b.x; } bool cmpy(node a,node b) {if(a.y==b.y)return a.x<b.x;return a.y<b.y; } int f(node a,node b) {return min(abs(a.x-b.x),abs(a.y-b.y)); } vector<edge> v[200010]; int main() {cin>>n;for(int i=1;i<=n;i++){cin>>a[i].x>>a[i].y;a[i].id=i;}sort(a+1,a+n+1,cmpx);for(int i=1;i<n;i++){v[a[i].id].push_back(edge{a[i+1].id,f(a[i],a[i+1])});v[a[i+1].id].push_back(edge{a[i].id,f(a[i],a[i+1])});}sort(a+1,a+n+1,cmpy);for(int i=1;i<n;i++){v[a[i].id].push_back(edge{a[i+1].id,f(a[i],a[i+1])});v[a[i+1].id].push_back(edge{a[i].id,f(a[i],a[i+1])});}priority_queue<edge> q;q.push(edge{1,0});for(int i=2;i<=n;i++)d[i]=1e9;while(!q.empty()){edge x=q.top();q.pop();if(x.s!=d[x.x])continue;for(int i=0;i<v[x.x].size();i++){edge y=v[x.x][i];if(d[y.x]>d[x.x]+y.s){d[y.x]=d[x.x]+y.s;q.push(edge{y.x,d[x.x]+y.s});}}}cout<<d[n]; }

祝大家AC大吉

总结

以上是生活随笔为你收集整理的[BZOJ4152][AMPPZ2014]The Captain题解的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。