当前位置：首页 > news >正文

【CF】1422D-Returning Home 题解

news 来源：原创 2024/9/20 9:34:46

传送门：1422D
标签：贪心

题目大意

Yura 已经走了很长时间，他计划尽快回家。为了做到这一点，Yura 可以利用城市周围的瞬间移动地点。把城市看作是一个 $n \times n$ 方形街区。Yura 需要从坐标 $s_x, s_y)$ 的街区移动到坐标 $f_x, f_y)$ 的街区。在一分钟内，Yura 可以移动到相邻的街区；换句话说，他可以在四个方向上移动。此外，城市中有 $m$ 个瞬间移动地点。他们的坐标已知并告诉 Yura。如果 Yura 所在的街区与瞬间移动地点的坐标相同，他可以在不花费时间的情况下移动到瞬间移动地点。帮助 Yura 找出回家所需的最短时间。

输入：第一行包含两个整数 $n$ 和 $m$ — 城市的大小和瞬间移动地点的数量（ $1 ≤ n ≤ 10^9$ , $0 ≤ m ≤ 10^5$ ）。下一行包含四个整数 $s_x, s_y, f_x, f_y$ — Yura 的初始位置坐标和他的家的坐标（ $1 ≤ s_x, s_y, f_x, f_y ≤ n$ ）。接下来的 $m$ 行各包含两个整数 $x_i, y_i$ — 第 $i$ 个瞬间移动地点的坐标（ $1 ≤ x_i, y_i ≤ n$ ）。
输出：在唯一行中输出返回所需的时间。

算法分析

很显然，当 $K = 2$ 时，我们可以从任何原子 $i$ （ $1 \leq i < N$ ）开始制作激发路线来激发所有原子。因此，对于 $K > 2$ ，我们可以通过切换键来制作路线。因此，有三种情况：
如果 $K = 0$ ，最优选择是只激发一个原子。尝试激发每个原子 $i$ 并使用前缀和计算获得的能量。
如果 $K \geq 2$ ，我们可以选择激发一个原子 $i$ （ $1 \leq i < N$ ），这会激发所有原子，或者仅激发最后一个原子（如果 $D$ 最低的话）。
如果 $K = 1$ ，需要分情况讨论，共有五种情况：

将 $E_{N - 1}$ 改变为 1。然后激发 $D_i$ 在 $1 \leq i < N$ 的原子。同时，如果能量增加，则激发原子 $N$ 。
将 $E_i$ 改变为 1 然后激发原子 $i$ 和 $i + 1$ （ $1 < i < N$ ）。激发 $i + 1$ 是最优的，因为如果不这样做，情况会比情况 1 更糟。
将 $E_1$ 改变为 3，然后激发 1 和 2。
将 $E_1$ 改变为 $N$ ，然后激发原子 $i$ （ $1 < i \leq N$ ）
将 $E_i$ 改变为 $i + 2$ ，然后激发原子 1（ $1 < i < N$ ）。只有当我们激发原子 1 时，这是最优的，否则它比情况 4 更差。

总体时间复杂度： $O (N)$

代码实现

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e6+10;
struct node
{int x,y,id;
}f[N];
struct node1
{int to,w,next;
}e[N];
int cnt,head[N];
int dist[N],vis[N];
int n,m;
void add(int x,int y,int z)
{cnt++;e[cnt].to=y;e[cnt].w=z;e[cnt].next=head[x];head[x]=cnt;
}
bool cmp1(node a,node b)
{return a.x<b.x;
}
bool cmp2(node a,node b)
{return a.y<b.y; 
}
void dij()
{memset(dist,0x3f,sizeof dist);dist[m+1]=0;priority_queue<pair<int,int> > q;q.push({0,m+1});while(q.size()){auto p=q.top();q.pop();int xx=p.second;if(vis[xx]) continue;vis[xx]=1;for(int i=head[xx];i;i=e[i].next){int yy=e[i].to;if(dist[yy]>dist[xx]+e[i].w){dist[yy]=dist[xx]+e[i].w;q.push({-dist[yy],yy});}}}
}
signed main()
{cin>>n>>m;int sx,sy,ex,ey;cin>>sx>>sy>>ex>>ey;for(int i=1;i<=m;i++){int x,y;cin>>x>>y;f[i].x=x,f[i].y=y,f[i].id=i;add(m+1,i,min(abs(x-sx),abs(y-sy)));add(i,m+1,min(abs(x-sx),abs(y-sy)));add(m+2,i,abs(x-ex)+abs(y-ey));add(i,m+2,abs(x-ex)+abs(y-ey));}add(m+1,m+2,abs(sx-ex)+abs(sy-ey));add(m+2,m+1,abs(sx-ex)+abs(sy-ey));sort(f+1,f+m+1,cmp1);for(int i=2;i<=m;i++){int id1=f[i-1].id,id2=f[i].id;int w=min(abs(f[i].x-f[i-1].x),abs(f[i].y-f[i-1].y));add(id1,id2,w);add(id2,id1,w);}sort(f+1,f+m+1,cmp2);for(int i=2;i<=m;i++){int id1=f[i-1].id,id2=f[i].id;int w=min(abs(f[i].x-f[i-1].x),abs(f[i].y-f[i-1].y));add(id1,id2,w);add(id2,id1,w);}dij();cout<<dist[m+2]<<'\n';
}