CodeForces - 1422D - Returning Home 建图

CodeForces - 1422D - Returning Home 建图

题意：给出起点和终点和m个跳跃点，跳跃点的定义是：只要主人公当前位置$(x,y)$的横坐标或纵坐标最少一个与跳跃点坐标$(x_i,y_i)$的相同就可以直接到跳跃点上。
想不出来 又是抄的题解

思路：由于在x坐标下，可以随意到达该x坐标下的任何的跳跃点，花费为0，所以将x坐标拆成m个点，只有跳到不同的x坐标下才会产生花费。同理y坐标。

拆顶点：规定起点为$0$,终点为$3m+1$,原先的m个跳跃点对应点集$[1,m]$，把$x$轴拆成点集$[m+1,2m]$,$y$轴拆成点集$[2m+1,3m]$

建图：
共有以下几种可以到达的情况：
1.起点到跳跃点：起点只要到达跳跃点对应的x或y坐标即可（然后就能直接跳来跳去），所以起点与两轴连单向边（从跳跃点回到起点无意义，不连也可以）
2.跳跃点到终点：由于终点不是跳跃点，所以跳跃点到终点的权值是哈密顿距离，也是连单向边（从终点回去无意义，不连也可以）

3.$x$轴之间：x轴之间显然是可以互相到达的，把$x$坐标单独取出来，没必要连$O(m^2)$个边，只需要连$O(m)$条边，比如$x$集合$[3,7,5,6]$，只需要在3和5之间连，5和6之间连，6和7之间连，就互相可达了，换句话说，连最少的边，使它强连通即可，排序即可。必须连双向边
4.$y$轴之间：同理

5.跳跃点到$x$轴：假设跳跃点在$(x,y)$，将它自身和拆出来的x轴上对应的坐标连起来，花费为0，表示跳跃点到该x坐标无需花费，必须连双向边
6.跳跃点到$y$轴：同理

代码：

const int maxn=4e6+7;
const int INF=0x3f3f3f3f;
const ll INFF=1e18;
struct qnode
{
    int v;ll c;qnode(int _v=0,ll _c=0):v(_v),c(_c){
    }bool operator< (const qnode &r)const{
    return c>r.c;}
};
struct node{
    int x,y;}p[maxn];
struct Edge{
    int v,next;ll cost;}edge[maxn];
int tol,head[maxn],n,m,sx,sy,fx,fy,x[maxn],y[maxn],a[maxn],b[maxn];
ll d[maxn];
bool vis[maxn];
ll dijkstra()
{
    mem(vis,false);rep(i,0,3*m+1)d[i]=INFF;priority_queue<qnode> q;while(!q.empty())q.pop();d[0]=0;q.push(qnode(0,0));qnode tmp;while(!q.empty()){
    tmp=q.top();q.pop();int u=tmp.v;if (vis[u])continue;vis[u]=true;for (int i=head[u];i!=-1;i=edge[i].next){
    int v=edge[i].v;int cost=edge[i].cost;if (!vis[v]&&d[v]>d[u]+cost){
    d[v]=d[u]+cost;q.push(qnode(v,d[v]));}}}return d[3*m+1];
}
void add(int u,int v,int w){
    edge[tol].v=v;edge[tol].cost=w;edge[tol].next=head[u];head[u]=tol++;}
void init()
{
    tol=0;mem(head,-1);
}
int main()
{
    init();scanf("%d%d",&n,&m);scanf("%d%d%d%d",&sx,&sy,&fx,&fy);rep(i,1,m){
    scanf("%d%d",&x[i],&y[i]);a[i]=x[i];b[i]=y[i];}sort(a+1,a+1+m);sort(b+1,b+1+m);add(0,3*m+1,abs(sx-fx)+abs(sy-fy));rep(i,1,m)//起点到跳跃点{
    add(0,i+m,abs(sx-a[i]));add(0,i+2*m,abs(sy-b[i]));}rep(i,2,m)//x轴之间+y轴之间{
    add(i+m,i+m-1,abs(a[i]-a[i-1]));add(i+m-1,i+m,abs(a[i]-a[i-1]));add(i+2*m,i+2*m-1,abs(b[i]-b[i-1]));add(i+2*m-1,i+2*m,abs(b[i]-b[i-1]));}rep(i,1,m)//跳跃点和终点{
    add(i,3*m+1,abs(x[i]-fx)+abs(y[i]-fy));}rep(i,1,m)//跳跃点到x轴和y轴{
    int pos=lower_bound(a+1,a+1+m,x[i])-a;add(i,pos+m,0);add(pos+m,i,0);pos=lower_bound(b+1,b+1+m,y[i])-b;add(i,pos+2*m,0);add(pos+2*m,i,0);}WW(dijkstra());return 0;
}