BZOJ 1706 [usaco2007 Nov]relays 奶牛接力跑

题目大意

给你一个N个点M条边的无向图，求刚好走k条边的从S到T的最短路。

这题需要使用到一种叫做倍增Floyd的算法：令$dis_{k,i,j}$表示从i到j走$2^k$步的最短距离，此时可以一层一层从低向上进行更新，最终用k二进制拆分'1'位上的dis值更新一下答案就可以了。

注意这里遇到了一个和之前一样的问题：

最终的答案$res_{i,j}$是用$dis_{k,i,j}$进行更新的。在更新的时候它们会得到一个新的矩阵，这个新的矩阵万万不可在求得过程中直接覆盖$res_{i,j}$数组！这样的话会造成重复利用的混乱，而且很难debug。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,S,T,u[110],v[110],w[110],st[210],ref[210],tot;
int dis[30][210][210],res[210][210],tmp[210][210];
void floyd()
{
	for(int l=1;(1ll<<l)<=n;++l)
		for(int k=1;k<=tot;++k)
			for(int i=1;i<=tot;++i)
				for(int j=1;j<=tot;++j)
					dis[l][i][j]=min(dis[l][i][j],dis[l-1][i][k]+dis[l-1][k][j]);
	for(int i=1;i<=tot;++i) res[i][i]=0;
	for(int l=0;(1ll<<l)<=n;++l) if((1ll<<l)&n)
	{
		for(int i=1;i<=tot;++i) for(int j=1;j<=tot;++j) tmp[i][j]=0x3f3f3f3f;
		for(int k=1;k<=tot;++k)
			for(int i=1;i<=tot;++i)
				for(int j=1;j<=tot;++j)
					tmp[i][j]=min(tmp[i][j],res[i][k]+dis[l][k][j]);
		for(int i=1;i<=tot;++i) for(int j=1;j<=tot;++j) res[i][j]=tmp[i][j];
	}
}
int main()
{
	memset(dis,0x3f,sizeof dis);
	memset(res,0x3f,sizeof res);
	scanf("%d%d%d%d",&n,&m,&S,&T);
	for(int i=1;i<=m;++i) scanf("%d%d%d",w+i,u+i,v+i),st[i]=u[i],st[m+i]=v[i];
	sort(st+1,st+(m<<1)+1);
	for(int i=1;i<=(m<<1);++i) if(st[i]!=st[i-1]) ref[++tot]=st[i];
	for(int i=1;i<=m;++i)
	{
		int tx=lower_bound(ref+1,ref+tot+1,u[i])-ref,ty=lower_bound(ref+1,ref+tot+1,v[i])-ref;
		dis[0][tx][ty]=dis[0][ty][tx]=min(dis[0][tx][ty],w[i]);
	}
	m<<=1;
	floyd();
	S=lower_bound(ref+1,ref+tot+1,S)-ref;
	T=lower_bound(ref+1,ref+tot+1,T)-ref;
	printf("%d\n",res[S][T]);
	return 0;
}