P6399 [COI 2008] TAMNICA
在没有打破墙的时候，任意两点 $x,y$ 的距离应该是 $|x-y|$，所以走破了的墙一定是最优的，那我们就可以把起点、终点和打破了的墙的两侧作为关键点跑一遍最短路。
现在问题在于怎么求墙的另一侧，如图：
我们把数字按 $2,4,6,8,\cdots$ 的长度分组，每一组又分为左右两个部分。
设当前数字为 $x$，$x$ 所在的组为 $c$，那就满足 $c^2-c+1\le x\le c^2+c$，解得 $c=\lfloor \frac{\sqrt{4x-3}+1}{2}\rfloor $。观察图不难发现，如果 $x$ 在当前组的左边部分，那墙后面的数字就应该是 $x-(4c-5)$；如果 $x$ 在当前组的右边部分，那墙后面的数字就应该是 $x-(4c-3)$，就可以得到代码：
C++
int geta(int x){
int c=((int)(sqrtl(4*x-3))+1)/2;
int l=c*c-c+1,r=c*c+c;
if(x*2<=l+r) return x-(4*c-5);
else return x-(4*c-3);
}之后就是建图，因为关键点比较大，所以要把关键点存下来后离散化：
C++
a[++n]=1,b[n]=1;
a[++n]=ed,b[n]=ed;
for(int i=1;i<=k;i++){
int x,y;
cin>>x;
y=geta(x);
a[++n]=x,b[n]=x,a[++n]=y,b[n]=y;
}
sort(b+1,b+1+n);然后建边，破了的墙的两侧直接连边权为 $1$ 的边，然后所有关键点排序一下，相邻的连边：
C++
for(int i=3;i<=n;i+=2){
int x=lower_bound(b+1,b+1+n,a[i])-b,y=lower_bound(b+1,b+1+n,a[i+1])-b;
g[x].push_back({y,1});
g[y].push_back({x,1});
}
for(int i=2;i<=n;i++){
g[i].push_back({i-1,b[i]-b[i-1]});
g[i-1].push_back({i,b[i]-b[i-1]});
}最后跑一边最短路，输出答案即可。
完整代码：
C++
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int ed,k,n;
int a[N],b[N],dis[N];
struct node{
int v,w;
bool operator<(const node &x)const{return w>x.w;}
};
vector<node> g[N];
int geta(int x){
int c=((int)(sqrtl(4*x-3))+1)/2;
int l=c*c-c+1,r=c*c+c;
if(x*2<=l+r) return x-(4*c-5);
else return x-(4*c-3);
}
void dj(){
priority_queue<node> q;
memset(dis,0x3f,sizeof dis);
dis[1]=0;
q.push({1,0});
while(q.size()){
int u=q.top().v,d=q.top().w;
q.pop();
if(d>dis[u]) continue;
for(auto x:g[u]){
int v=x.v,w=x.w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
q.push({v,d+w});
}
}
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>ed>>k;
a[++n]=1,b[n]=1;
a[++n]=ed,b[n]=ed;
for(int i=1;i<=k;i++){
int x,y;
cin>>x;
y=geta(x);
a[++n]=x,b[n]=x,a[++n]=y,b[n]=y;
}
sort(b+1,b+1+n);
for(int i=3;i<=n;i+=2){
int x=lower_bound(b+1,b+1+n,a[i])-b,y=lower_bound(b+1,b+1+n,a[i+1])-b;
g[x].push_back({y,1});
g[y].push_back({x,1});
}
for(int i=2;i<=n;i++){
g[i].push_back({i-1,b[i]-b[i-1]});
g[i-1].push_back({i,b[i]-b[i-1]});
}
dj();
cout<<dis[lower_bound(b+1,b+1+n,ed)-b];
return 0;
}
Comments NOTHING