挺有趣的分塊的題目。

直接暴力建邊SPFA貌似是$O(nm)$的。

然后考慮分塊，$\sqrt n$一下用虛擬節點輔助連邊，

以上的直接暴力連邊即可。

然后卡卡時間，卡卡空間。

終于在UOJ上T掉辣。

遂棄療

#include <map> #include <cmath> #include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define F(i,j,k) for (int i=j;i<=k;++i) #define D(i,j,k) for (int i=j;i>=k;--i) #define ll long long #define mp make_pair #define inf 0x3f3f3f3f #define maxn 30005int n,m,b[maxn],p[maxn],cnt=0; int num[maxn][101],T,s,t; int h[maxn*101],to[maxn*500],ne[maxn*500],en=0,dis[maxn*101]; int w[maxn*500],inq[maxn*101]; queue <int> q; void add(int a,int b,int c) {to[en]=b;ne[en]=h[a];w[en]=c;h[a]=en++;}void SPFA() {memset(dis,0x3f,sizeof dis);dis[s]=0;inq[s]=1;q.push(s);while (!q.empty()){int x=q.front();q.pop();inq[x]=0;for (int i=h[x];i>=0;i=ne[i])if (dis[to[i]]>dis[x]+w[i]){dis[to[i]]=dis[x]+w[i];if (!inq[to[i]]){inq[to[i]]=1;q.push(to[i]);}}}if (dis[t]!=inf) printf("%d\n",dis[t]);else printf("-1\n");return; }int read() {int x=0,f=1; char ch=getchar();while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch=getchar();}while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}return x*f; }int main() {memset(h,-1,sizeof h);n=read();m=read();T=min((int)sqrt(n),100);cnt=n;F(i,1,n) F(j,1,T) num[i][j]=++cnt;F(i,1,m) b[i]=read(),p[i]=read(),b[i]++;s=b[1];t=b[2];F(i,1,n) F(j,1,T){if (i+j<=n) add(num[i][j],num[i+j][j],1);if (i-j>0) add(num[i][j],num[i-j][j],1);add(num[i][j],i,0);}F(i,1,m){if (p[i]<=T) add(b[i],num[b[i]][p[i]],0);else{for (int j=1;b[i]+j*p[i]<=n;j++) add(b[i],b[i]+j*p[i],j);for (int j=1;b[i]-j*p[i]>=1;j++) add(b[i],b[i]-j*p[i],j);}}SPFA();return 0; }

　　

轉載于:https://www.cnblogs.com/SfailSth/p/6776435.html

總結

以上是生活随笔為你收集整理的BZOJ 4070 [Apio2015]雅加达的摩天楼 ——分块 SPFA的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。