标签：spfa include front def += png spl info int
题意
n
题解
暴力的话就是直接建边跑spfa最短路
然而直接建边看上去复杂度正确,实际最多会建$n^2$条边,
看上去复杂度正确如何不试一试,
$dis[x][y]$表示位置$x$有一只跳跃长度为y的狗
炸空间十分严重30000*30000开不下
,考虑分块,这样就不炸空间了
$dis[0][x][y]$表示位置$x$有一只跳跃长度为y的狗
$dis[1][x][y]$表示$id$为$x$的狗目前跳到了能跳的第$y$个位置
以200为分界线dis[2][30000][200]就行了
由于数据比较水,你分块完就AC了,只是一种优化的暴力就可以水过这个题
但这实在不失为优化空间的一种好方法
水过的代码
#includeusing namespace std;
#define ll long long
#define A 31000
#define maxn 215
ll dis[2][A][maxn],vis[A][maxn],rec[A],b[A],p[A],st[A];
ll flag[2][A][maxn];
ll n,m,ans;
vector v[A];
vector dog[A];
struct node{
ll opt,pla,x;
node(){}
node(const ll &a,const ll &b,const ll &c){opt=a,pla=b,x=c;}
};
queue q;
void update(ll x,ll d){
// printf("x=%lld d=%lld\n",x,d);
if(!rec[x]){
for(ll i=0;i){
ll h=dog[x][i];
if(dis[1][h][st[h]]>d){
dis[1][h][st[h]]=d;
q.push(node(1,h,st[h]));
}
}
for(ll i=1;i200;i++){
if(vis[x][i]){
if(dis[0][x][i]>d){
dis[0][x][i]=d;
// printf("**********i=%lld\n",i);
q.push(node(0,x,i));
}
}
}
rec[x]=1;
}
}
void spfa(){
memset(dis,0x3f,sizeof(dis));
if(p[0]>=200){
q.push(node(1,0,st[p[0]]));
dis[1][0][st[p[0]]]=0;
}
else {
q.push(node(0,b[0],p[0]));
dis[0][b[0]][p[0]]=0;
}
update(b[0],0);
while(!q.empty()){
node u=q.front();
q.pop();
flag[u.opt][u.pla][u.x]=0;
ll d=dis[u.opt][u.pla][u.x];
// printf("dis=%lld opt=%lld pla=%lld x=%lld\n",dis[u.opt][u.pla][u.x],u.opt,);
if(u.opt==0){
if(u.pla+u.xn)
if(dis[0][u.pla+u.x][u.x]>d+1){
dis[0][u.pla+u.x][u.x]=d+1;
if(!flag[0][u.pla+u.x][u.x]){
flag[0][u.pla+u.x][u.x]=1;
q.push(node(0,u.pla+u.x,u.x));
}
update(u.pla+u.x,d+1);
}
if(u.pla-u.x>=0)
if(dis[0][u.pla-u.x][u.x]>d+1){
dis[0][u.pla-u.x][u.x]=d+1;
if(!flag[0][u.pla-u.x][u.x]){
flag[0][u.pla-u.x][u.x]=1;
q.push(node(0,u.pla-u.x,u.x));
}
update(u.pla-u.x,d+1);
}
}
else{
if(u.x>=1)
if(dis[1][u.pla][u.x-1]>d+1){
dis[1][u.pla][u.x-1]=d+1;
if(!flag[1][u.pla][u.x-1]){
flag[1][u.pla][u.x-1]=1;
q.push(node(1,u.pla,u.x-1));
}
update(v[u.pla][u.x-1],d+1);
}
if(u.x+1v[u.pla].size())
if(dis[1][u.pla][u.x+1]>d+1){
dis[1][u.pla][u.x+1]=d+1;
if(!flag[1][u.pla][u.x+1]){
flag[1][u.pla][u.x+1]=1;
q.push(node(1,u.pla,u.x+1));
}
update(v[u.pla][u.x+1],d+1);
}
}
}
}
int main(){
scanf("%lld%lld",&n,&m);
for(ll i=0;i){
scanf("%lld%lld",&b[i],&p[i]);
if(p[i]>=200){
dog[b[i]].push_back(i);
ll k=b[i];
while(k>=p[i]) k-=p[i];
while(kn){
v[i].push_back(k);
if(k==b[i]){
st[i]=v[i].size()-1;
}
k+=p[i];
}
}
else vis[b[i]][p[i]]=1;
}
spfa();
ans=0x3f3f3f3f;
if(p[1]>=200){
ans=min(ans,dis[1][1][st[1]]);
}
else {
ans=min(ans,dis[0][b[1]][p[1]]);
}
if(ans>=1000000)
printf("-1\n");
else printf("%lld\n",ans);
}
View Code
然而当p很小还是会建很多条边,如果p全是1你会挂仍然会被卡成sb
作为一个有脸的人是需要打正解的
正解是分块+建虚点
APIO2015雅达加的摩天楼
标签：spfa include front def += png spl info int
原文地址：https://www.cnblogs.com/znsbc-13/p/11746997.html