假设当前位于$A(x,y)$，将坐标系按上下左右、(左/右)(上/下)分为八块
引理：存在一组最优解，每次均移动到某一块中距离$(x,y)$最近的某点
记$d(A,B)$为$A$到$B$的切比雪夫距离，即$\max(|x_{A}-x_{B}|,|y_{A}-y_{B}|)$
假设移动到的点为$B$，而该块中最近的某点为$C$，则$d(A,C),d(B,C)<d(A,B)$
（前者根据定义显然，后者考虑$dis(A,B)$中较大的一维即可）
换言之，有$2^{d(A,C)}+2^{d(B,C)}\le 2^{d(A,B)}$，从$C$经过不劣，即得证
上下左右四部分显然该点唯一，可以直接连边
(左/右)(上/下)四部分建立一个虚点，并从虚点向这些取到最近距离的点连边
此时，虽然图中有$O(n^{2})$条边，但实际有边权的边仅有$O(n)$条
考虑dijkstra求最短路，并用（手写）bitset维护距离
对于带权边，可以$O(\frac{n}{\omega})$更新；对于不带权边，可以直接更新，且至多$O(n)$次
每次取出最小距离可以用堆/线段树维护，单次更新的复杂度为$O(\frac{n\log n}{\omega})$
综上，总复杂度为$O(n^{2}+\frac{n^{2}\log n}{\omega})$，可以通过
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define L (k<<1)
4 #define R (L|1)
5 #define mid (l+r>>1)
6 typedef unsigned long long ull;
7 const int N=10100,M=90005,oo=0x3f3f3f3f;
8 int n,V,x[N],y[N],a[N][8],id[N][8],vis[M],from[M],f[M<<2];
9 ull d[M][N>>6];pair<int,int>pos[M];
10 vector<int>ans,v[N][8];
11 int dis(int i,int j){
12 return max(abs(x[i]-x[j]),abs(y[i]-y[j]));
13 }
14 int dir(int i,int j){
15 int dx=(x[i]==x[j] ? 2 : x[i]<x[j]);
16 int dy=(y[i]==y[j] ? 2 : y[i]<y[j]);
17 return dx*3+dy;
18 }
19 bool cmp(int x,int y){
20 for(int i=(N>>6)-1;i>=0;i--)
21 if (d[x][i]!=d[y][i])return d[x][i]<d[y][i];
22 return 0;
23 }
24 void add(int x,int y){
25 memcpy(d[0],d[x],sizeof(d[0]));
26 if (y<0)return;
27 ull s=((ull)1<<(y&63));
28 y>>=6,d[0][y]+=s;
29 if (d[0][y]<d[x][y]){
30 y++;
31 while (d[0][y]==(ull)-1)d[0][y++]=0;
32 d[0][y]++;
33 }
34 }
35 void up(int k){
36 if ((!f[L])||(!f[R]))f[k]=(f[L]|f[R]);
37 else f[k]=(cmp(f[L],f[R]) ? f[L] : f[R]);
38 }
39 void build(int k,int l,int r){
40 if (l==r){
41 f[k]=(l==1);
42 return;
43 }
44 build(L,l,mid),build(R,mid+1,r);
45 up(k);
46 }
47 void update(int k,int l,int r,int x,int y){
48 if (l==r){
49 f[k]=y;
50 return;
51 }
52 if (x<=mid)update(L,l,mid,x,y);
53 else update(R,mid+1,r,x,y);
54 up(k);
55 }
56 int main(){
57 scanf("%*d%*d%d",&n);
58 for(int i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]);
59 V=n;
60 memset(a,0x3f,sizeof(a));
61 for(int i=1;i<=n;i++){
62 for(int j=1;j<=n;j++){
63 int D=dis(i,j),P=dir(i,j);
64 if (P==8)continue;
65 if (D<a[i][P])a[i][P]=D,v[i][P].clear();
66 if (D==a[i][P])v[i][P].push_back(j);
67 }
68 for(int P=0;P<8;P++)
69 if (!v[i][P].empty()){
70 id[i][P]=++V;
71 pos[V]=make_pair(i,P);
72 }
73 }
74 for(int i=2;i<=V;i++)d[i][(N>>6)-1]=-1;
75 build(1,1,V);
76 while (1){
77 int k=f[1];
78 if (k==n)break;
79 if (k<=n){
80 for(int P=0;P<8;P++)
81 if ((!vis[id[k][P]])&&(id[k][P])){
82 add(k,a[k][P]);
83 if (cmp(0,id[k][P])){
84 from[id[k][P]]=k;
85 memcpy(d[id[k][P]],d[0],sizeof(d[0]));
86 update(1,1,V,id[k][P],id[k][P]);
87 }
88 }
89 }
90 else{
91 int P=pos[k].second;
92 for(int i:v[pos[k].first][P])
93 if (!vis[i]){
94 from[i]=k,vis[i]=1;
95 memcpy(d[i],d[k],sizeof(d[i]));
96 update(1,1,V,i,i);
97 }
98 }
99 vis[k]=1,update(1,1,V,k,0);
100 }
101 for(int i=n;i!=1;i=from[i])
102 if (i<=n)ans.push_back(i);
103 ans.push_back(1);
104 reverse(ans.begin(),ans.end());
105 printf("%d\n",ans.size());
106 for(int i:ans)printf("%d ",i);
107 return 0;
108 }
View Code
标签：传态,frac,int,距离,隐形,loj2846,虚点,return,omega From： https://www.cnblogs.com/PYWBKTDA/p/16814326.html