传送门：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}$
- $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
*/
Comments | NOTHING