http://acm.hdu.edu.cn/showproblem.php?pid=6331
Problem Description There are n intersections in Bytetown, connected with m one way streets. Little Q likes sport walking very much, he plans to walk for q days. On the i-th day, Little Q plans to start walking at the si-th intersection, walk through at least ki streets and finally return to the ti-th intersection. Little Q’s smart phone will record his walking route. Compared to stay healthy, Little Q cares the statistics more. So he wants to minimize the total walking length of each day. Please write a program to help him find the best route.
题意：n（50）个点，m条边，q（10万）次询问，每次查询u到v至少经过k(1万)条边的最短路径。 思路： 不加优化的dp要 O ( n 3 ∗ k m a x ) O(n^3*k_{max}) O(n3∗kmax)，超时太多。 考虑分块，每块大小 M = k m a x = 100 M=\sqrt{k_{max}}=100 M=kmax =100,分成100块。 d1,d2,d3分别是恰好走k条边，恰好走 k ∗ M k*M k∗M条边，至少走k条边 d 1 ( k , i , j ) = m i n { d 1 ( k − 1 , i , x ) + d 1 ( 1 , x , j ) } d1(k,i,j)=min\{d1(k-1,i,x)+d1(1,x,j)\} d1(k,i,j)=min{d1(k−1,i,x)+d1(1,x,j)} k < = 100 k<=100 k<=100 d 2 ( k , i , j ) = m i n { d 2 ( k − 1 , i , x ) + d 2 ( 1 , x , j ) } d2(k,i,j)=min\{d2(k-1,i,x)+d2(1,x,j)\} d2(k,i,j)=min{d2(k−1,i,x)+d2(1,x,j)} k < = 100 k<=100 k<=100 d 3 ( k , i , j ) = m i n { d 1 ( k , i , x ) + d ( x , j ) } d3(k,i,j)=min\{d1(k,i,x)+d(x,j)\} d3(k,i,j)=min{d1(k,i,x)+d(x,j)} k < = 100 k<=100 k<=100 注意要更新到k==0的情况 或者 d 3 ( k , i , j ) = m i n { d 3 ( k , i , j ) , d 3 ( k + 1 , i , j ) } d3(k,i,j)=min\{d3(k,i,j),d3(k+1,i,j)\} d3(k,i,j)=min{d3(k,i,j),d3(k+1,i,j)},但要把 d 1 d1 d1和 d 3 d3 d3的k开到150而非100，原因如下：n=50，两点之间如果不走环最多走49条边，>49的话要么不可行，要么走环，有可能算至少走99条边的最短路时，恰好99条边到达不了，需要多开一个n的大小，保证可以到达。 处理询问时，枚举中间结点x，算u->x整块+x->v块内最小的。 预处理复杂度 O ( M n 3 ) O(Mn^3) O(Mn3),查询复杂度 O ( q ∗ n ) O(q*n) O(q∗n)
这篇blog讲的极好https://blog.csdn.net/weixin_42068627/article/details/81299321
#include<bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f int T,n,m,q; int d1[151][51][51],d2[101][51][51]; void dp() { for(int k=2;k<=150;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int x=1;x<=n;x++) d1[k][i][j]=min(d1[k-1][i][x]+d1[1][x][j],d1[k][i][j]); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) d2[1][i][j]=d1[100][i][j]; for(int k=2;k<=100;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int x=1;x<=n;x++) d2[k][i][j]=min(d2[k-1][i][x]+d2[1][x][j],d2[k][i][j]); for(int k=149;k>=0;k--) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int x=1;x<=n;x++) d1[k][i][j]=min(d1[k+1][i][j],d1[k][i][j]); } int main() { //freopen("input.in","r",stdin); cin>>T; while(T--) { int u,v,w; cin>>n>>m; memset(d1,INF,sizeof(d1)); memset(d2,INF,sizeof(d2)); for(int i=1;i<=n;i++)d1[0][i][i]=d2[0][i][i]=0; while(m--) { scanf("%d%d%d",&u,&v,&w); d1[1][u][v]=min(d1[1][u][v],w); } dp(); cin>>q; while(q--) { scanf("%d%d%d",&u,&v,&w); int ans=INF; for(int x=1;x<=n;x++) ans=min(ans,d2[w/100][u][x]+d1[w%100][x][v]); printf("%d\n",ans<INF?ans:-1); } } return 0; } #include<bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f int T,n,m,q; int d[51][51],d1[101][51][51],d2[101][51][51],d3[101][51][51]; void dp() { for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]); for(int k=2;k<=100;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int x=1;x<=n;x++) d1[k][i][j]=min(d1[k-1][i][x]+d1[1][x][j],d1[k][i][j]); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) d2[1][i][j]=d1[100][i][j]; for(int k=2;k<=100;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int x=1;x<=n;x++) d2[k][i][j]=min(d2[k-1][i][x]+d2[1][x][j],d2[k][i][j]); for(int k=0;k<=100;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int x=1;x<=n;x++) d3[k][i][j]=min(d3[k][i][j],d1[k][i][x]+d[x][j]); } int main() { //freopen("input.in","r",stdin); cin>>T; while(T--) { int u,v,w; cin>>n>>m; memset(d,INF,sizeof(d)); memset(d1,INF,sizeof(d1)); memset(d2,INF,sizeof(d2)); memset(d3,INF,sizeof(d3)); for(int i=1;i<=n;i++)d[i][i]=d1[0][i][i]=d2[0][i][i]=0; while(m--) { scanf("%d%d%d",&u,&v,&w); d1[1][u][v]=min(d1[1][u][v],w); d[u][v]=min(d[u][v],w); } dp(); cin>>q; while(q--) { scanf("%d%d%d",&u,&v,&w); int ans=INF; for(int x=1;x<=n;x++) ans=min(ans,d2[w/100][u][x]+d3[w%100][x][v]); printf("%d\n",ans<INF?ans:-1); } } return 0; }