传送门:D. Returning Home

题意

在二维平面上,给你起点和终点的坐标,你从起点出发,每秒可以上下左右选个方向移动一格。平面上还有$m$个传送门,若当前位置的 $x$或$y$ 与任意一个传送门的 $x$或$y$ 相同,则可以不花费时间立即到达该传送门。求起点到终点的最短时间。

思路

首先,从一个点到传送门,只移动了$x$$y$;从一个点到终点,必须移动$x$$y$。

设起点编号为$s$,第$i$个传送门为$p_i$,终点为$t$。

可将$s$,$p_i$,$t$,连边建图,然后用最短路算法解决。

连边时,根据不同情况考虑边权$w$的取值:
1. $s$->$p_i$ 或 $p_i$<->$p_j$($p_i$, $p_j$在$x$轴上相邻)。
只走$x$轴,走到$x$和传送门相等就直接传送。
$w= \begin{cases} 0, &if(y_1==y_2) \ \vert x_1-x_2 \vert,&else \end{cases}$
2. $s$->$p_i$ 或 $p_i$<->$p_j$($p_i$, $p_j$在$y$轴上相邻)。
只走$y$轴,走到$y$和传送门相等就直接传送。
$w= \begin{cases} 0, &if(x_1==x_2) \ \vert y_1-y_2 \vert,&else \end{cases}$

  1. $s$->$t$ 或 $p_i$->$t$。必须移动$x$和$y$。
    $w=\vert x_1-x_2 \vert + \vert y_1-y_2 \vert$

连完边直接跑$Dijkstra$算法就行了。

另外,说一下我wa的地方:路径为 $s$->$p_a,p_b,p_c$...->$t$ 的时间一定较短?
不一定,有可能起点直接到终点更短(比如传送门都在终点的后面,这时候去走传送门显然就浪费时间)。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10,inf=(1<<31)-1;
int n,m,head[N],cnt;
int bx,by,ex,ey,dis[N];
bool vis[N];
struct edge
{
    int to,w,next;
}e[7*N]; // 根据连边数量确定数组大小
void add(int x,int y,int z) // 加单向边
{
    e[cnt].to=y;
    e[cnt].w=z;
    e[cnt].next=head[x];
    head[x]=cnt++;
}
void add_edge(int x,int y,int z) // 加双向边
{
    add(x,y,z);
    add(y,x,z);
}
struct node
{
    int x,y,num; // num是点的编号
}p[N];
bool cmp1(node s1,node s2) // 按x升序,投影到x轴
{
    if(s1.x!=s2.x)return s1.x<s2.x;
    return s1.y<s2.y;
}
bool cmp2(node s1,node s2) // 按y升序,投影到y轴
{
    if(s1.y!=s2.y)return s1.y<s2.y;
    return s1.x<s2.x;
}
struct qnode
{
    int u,w;
    operator < (const qnode &a) const
    {
        return w>a.w;
    }
};
int dijkstra(int s,int t)
{
    priority_queue<qnode>q;
    for(int i=0;i<=m+1;i++)
        dis[i]=inf;
    dis[s]=0;
    q.push({s,0});
    while(!q.empty())
    {
        int u=q.top().u;q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i=head[u];~i;i=e[i].next)
        {
            int v=e[i].to;
            if(dis[u]+e[i].w<dis[v])
            {
                dis[v]=dis[u]+e[i].w;
                q.push({v,dis[v]});
            }
        }
    }
    return dis[t];
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m>>bx>>by>>ex>>ey;
    for(int i=1;i<=m;i++)
    {
        cin>>p[i].x>>p[i].y;
        p[i].num=i;
    }
    int d=abs(bx-ex)+abs(by-ey); // 起点到终点的距离
    if(m==0)printf("%d\n",d);
    else
    {
        memset(head,-1,sizeof(head));
        int s=0,t=m+1; // 起点编号s,终点编号t
        for(int i=1;i<=m;i++)
        {
            int w1=(p[i].y==by?0:abs(p[i].x-bx));
            int w2=(p[i].x==bx?0:abs(p[i].y-by));
            int w3=abs(p[i].x-ex)+abs(p[i].y-ey);
            add(s,i,w1); // 单向边,起点->传送门(只经过x轴)
            add(s,i,w2); // 单向边,起点->传送门(只经过y轴)
            add(i,t,w3); // 单向边,传送门->终点(必须经过x轴和y轴)
        }
        sort(p+1,p+m+1,cmp1); // x升序
        for(int i=2;i<=m;i++)
        {
            int u=p[i-1].num; // 传送门编号
            int v=p[i].num;
            int w=(p[i].y==p[i-1].y?0:abs(p[i].x-p[i-1].x));
            add_edge(u,v,w); // 双向边,传送门u<->传送门v(x轴上的相邻传送门)
        }
        sort(p+1,p+m+1,cmp2); // y升序
        for(int i=2;i<=m;i++)
        {
            int u=p[i-1].num; // 传送门编号
            int v=p[i].num;
            int w=(p[i].x==p[i-1].x?0:abs(p[i].y-p[i-1].y));
            add_edge(u,v,w); // 双向边,传送门u<->传送门v(y轴上的相邻传送门)
        }
        // 可能的最短路径
        // (1)起点->传送门p1,p2,p3...->终点,ans=disjktra(s,t)
        // (2)起点->终点,ans=d
        int ans=min(dijkstra(s,t),d);
        printf("%d\n",ans);
    }
    return 0;
}
/*
5 0
1 1 5 5
ans:8
*/