HDU6331 Walking Plan

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\ast k_{max})$O(n3∗kmax​)，超时太多。
考虑分块，每块大小 $M=\sqrt{k_{max}}=100$M=kmax​ ​=100,分成100块。
d1,d2,d3分别是恰好走k条边，恰好走 $k\ast M$k∗M条边，至少走k条边
$d1(k,i,j)=min\left\{d1\right(k-1,i,x)+d1(1,x,j\left)\right\}$d1(k,i,j)=min{d1(k−1,i,x)+d1(1,x,j)} $k\&lt;=100$k<=100
$d2(k,i,j)=min\left\{d2\right(k-1,i,x)+d2(1,x,j\left)\right\}$d2(k,i,j)=min{d2(k−1,i,x)+d2(1,x,j)} $k\&lt;=100$k<=100
$d3(k,i,j)=min\left\{d1\right(k,i,x)+d(x,j\left)\right\}$d3(k,i,j)=min{d1(k,i,x)+d(x,j)} $k\&lt;=100$k<=100 注意要更新到k==0的情况
或者 $d3(k,i,j)=min\left\{d3\right(k,i,j),d3(k+1,i,j\left)\right\}$d3(k,i,j)=min{d3(k,i,j),d3(k+1,i,j)},但要把 $d1$d1和 $d3$d3的k开到150而非100，原因如下：n=50，两点之间如果不走环最多走49条边，>49的话要么不可行，要么走环，有可能算至少走99条边的最短路时，恰好99条边到达不了，需要多开一个n的大小，保证可以到达。
处理询问时，枚举中间结点x，算u->x整块+x->v块内最小的。
预处理复杂度 $O\left(M{n}^3\right)$O(Mn3),查询复杂度 $O(q\ast 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;
}