【Codeforces Round #515 (Div. 3) F. Yet another 2D Walking】 建图+Dijkstra

F. Yet another 2D Walking

题意

题意就是给你一个二维坐标系，之后给你n个点$(x_i,y_i)$，每个点的等级为$max(x_i,y_i)$,最初起点在(0,0)，想走到高一级的点，就要走完本等级所有的点，问最终走完所有点的最小移动距离（每一步只能向上下左右四个位置移动）

做法

看图可以知道一个特性，由某个等级向下一个等级转移的时候，一定要先转移到最左上的点或者最右下的点，不然走到中间还是要来回走一圈，所以如果我们知道这个特性，我们就可以把这关键点抠出来建图，设dis为两点之间距离，那么我们只要对
$mi{n}_1与ma{x}_1连边，边权为dis(mi{n}_1,mi{n}_2)+dis(mi{n}_2,ma{x}_1)$ 表示要走完本等级再到下一级
$mi{n}_1与ma{x}_2连边，边权为dis(mi{n}_1,mi{n}_2)+dis(mi{n}_2,ma{x}_2)$ 表示要走完本等级再到下一级]
$mi{n}_2与ma{x}_1连边，边权为dis(mi{n}_1,mi{n}_2)+dis(mi{n}_1,ma{x}_1)$ 表示要走完本等级再到下一级
$mi{n}_2与ma{x}_2连边，边权为dis(mi{n}_1,mi{n}_2)+dis(mi{n}_1,ma{x}_2)$ 表示要走完本等级再到下一级

之后再对最后一层建一个超级汇点，最后一层的两个关键点$fi{n}_1,fi{n}_2$距离汇点的距离为dis(fin_1,fin_2)，表示走完所有点。
之后以(0,0)为起点，跑一遍dij即可解决本问题。
代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;typedef long long ll;
typedef unsigned long long ull;
typedef pair <ll, ll> pll;const int maxn = 1e6+5;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;struct data
{
    ll x,y,id;
}pp[maxn];
bool cmp(const data &a,const data &b)
{
    if(a.id!=b.id) return a.id<b.id;else return a.y*b.x>a.x*b.y;
}
ll abs_(ll x)
{
    if(x<0) return -x;return x;
}
ll cal(ll x1,ll y1,ll x2,ll y2)
{
    return abs_(x1-x2)+abs_(y1-y2);
}
struct P
{
    int to;ll cost;bool operator < (const P & a) const{
    return cost>a.cost;}
};
struct node
{
    int to;ll val;int nxt;
}edge[maxn];
int head[maxn],tot,pcnt;//head和tot记得重置，head重置为-1
bool vis[maxn];//每次在dij里面初始化为0
ll dis[maxn],tmp1;//根据题意初始化为inf可能int可能longlong
void addedge(int x,int y,ll val)
{
    edge[tot].to=y;edge[tot].val=val;edge[tot].nxt=head[x];head[x]=tot++;
}
void Dijkstra()
{
    memset(vis,0,sizeof(vis));fill(dis,dis+pcnt+2,LL_INF);dis[1]=0;dis[2]=0;priority_queue<P>q;q.push(P{
    1,0});q.push(P{
    2,0});while(!q.empty()){
    P p1=q.top();q.pop();int u=p1.to;if(vis[u])continue;vis[u]=1;for(int i=head[u];i+1;i=edge[i].nxt){
    int v=edge[i].to;if(vis[v])continue;if(dis[v]>dis[u]+edge[i].val){
    dis[v]=dis[u]+edge[i].val;q.push(P{
    v,dis[v]});}}}
}
int main()
{
    int n,x,y;scanf("%d",&n);pp[0].x=0;pp[0].y=0;pp[0].id=0;for(int i=1;i<=n;i++){
    scanf("%lld%lld",&pp[i].x,&pp[i].y);pp[i].id=max(pp[i].x,pp[i].y);}memset(head,-1,sizeof(head));sort(pp,pp+1+n,cmp);pll pre1,pre2;int pre1id=++pcnt;int pre2id=++pcnt;pre1.first=0;pre1.second=0;pre2.first=0;pre2.second=0;for(int i=1;i<=n;i++){
    vector<data>tmp;tmp.push_back(pp[i]);i++;for(int j=i;j<=n;j++,i++){
    if(pp[j].id!=pp[j-1].id){
    i--;break;}tmp.push_back(pp[j]);}int sz=tmp.size();data l=tmp[0];data r=tmp[sz-1];int lid=++pcnt;int rid=++pcnt;tmp1=cal(pre1.first,pre1.second,pre2.first,pre2.second);addedge(pre1id,lid,tmp1+cal(pre2.first,pre2.second,l.x,l.y));addedge(pre1id,rid,tmp1+cal(pre2.first,pre2.second,r.x,r.y));addedge(pre2id,lid,tmp1+cal(pre1.first,pre1.second,l.x,l.y));addedge(pre2id,rid,tmp1+cal(pre1.first,pre1.second,r.x,r.y));pre1id=lid;pre1.first=l.x,pre1.second=l.y;pre2id=rid;pre2.first=r.x,pre2.second=r.y;}++pcnt;addedge(pre1id,pcnt,cal(pre1.first,pre1.second,pre2.first,pre2.second));addedge(pre2id,pcnt,cal(pre1.first,pre1.second,pre2.first,pre2.second));Dijkstra();printf("%lld\n",dis[pcnt]);return 0;
}