「USACO 2007 Nov. Gold」Cow Relays奶牛接力赛 - 动态规划+矩阵快速幂

题目大意

求出从S->E经过K条边的最短路。

---

初步想法

我们可以想到一个显然的思路（动规）：
设$f[i,j]$表示经过i条边到达j点的最短路径长度。

$$f[i,j]=\min_{k=1}^{n}\{f[i-1,k]+map[k,j]\}$$

时间复杂度：$O(n^2k)\quad n\le100\quad k<=10^6$
明显超时。

---

优化方案

能否对动规进行优化呢？
观察原式的转移只与上一个状态i-1与k有关，而i-1是定值，故只与k有关。
再观察数据范围，n比较小而k比较大。
再观察方程，是不是和这个方程长得很像？

$$g[i,j]=\sum_{k=1}^{n}g[i-1,j]\times map[k,j]$$

这正是经过k条边最短路计数的方程。
没错，我们可以类似的使用矩阵快速幂进行优化。

---

定义矩阵乘法：

$$C[i,j]=\min_{k=1}^{n}\{A[i,k]+B[k,j]\}$$

这个似乎与floyd长得有点像？但是并不是floyd，状态意义不一样。
然后我们就可以进行愉快的矩阵快速幂啦。
注意对原图的点进行离散化，点的范围就变成了边的范围。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<map>
using namespace std;
inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
typedef long long LL;
const int maxn=105;
struct Matrix {
	LL n,m,a[maxn][maxn];
	Matrix(LL n,LL m) {
		this->n=n;
		this->m=m;
		memset(a,0,sizeof(a));
	}
	Matrix(LL n,LL m,char E) { //单位矩阵
		this->n=n;
		this->m=m;
		memset(a,0,sizeof(a));
		for(int i=1; i<=n; i++)a[i][i]=1;
	}
	void init(LL n,LL m) {
		this->n=n;
		this->m=m;
		memset(a,0,sizeof(a));
	}
	LL* operator [] (const LL x) {
		return a[x];
	}
	Matrix operator = (Matrix b) {
		init(b.n,b.m);
		for(int i=1; i<=b.n; i++)
			for(int j=1; j<=b.m; j++)
				a[i][j]=b[i][j];
	}
	Matrix operator + (Matrix& b) {
		for(int i=1; i<=b.n; i++)
			for(int j=1; j<=b.m; j++)
				a[i][j]+=b[i][j];
	}
	void operator += (Matrix& b) {
		*this=*this+b;
	}
	Matrix operator - (Matrix& b) {
		for(int i=1; i<=b.n; i++)
			for(int j=1; j<=b.m; j++)
				a[i][j]-=b[i][j];
	}
	void operator -= (Matrix& b) {
		*this=*this-b;
	}
	Matrix operator * (LL k) {
		for(int i=1; i<=n; i++)
			for(int j=1; j<=m; j++)
				a[i][j]*=k;
	}
	void operator *= (LL k) {
		*this=*this*k;
	}
	Matrix operator * (Matrix& b) {
		Matrix c(n,b.m);
		for(int i=1; i<=n; i++)
			for(int j=1; j<=b.m; j++) {
				c[i][j]=0;
				LL tmp=1e17;
				for(int k=1; k<=m; k++)
					if(a[i][k]!=0&&b[k][j]!=0)tmp=min(tmp,a[i][k]+b[k][j]);
				if(tmp!=1e17)c[i][j]=tmp;
			}
		return c;
	}
	void operator *= (Matrix& b) {
		*this=*this*b;
	}
	Matrix operator ^ (LL b) {
		Matrix ans=*this,a=*this;
		b--;
		while(b>0) {
			if(b&1)ans=ans*a;
			a*=a;
			b>>=1;
		}
		return ans;
	}
	void Output() {
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=m; j++)
				printf("%lld ",a[i][j]);
			putchar('\n');
		}
	}
};
int n,m,Start,End,step=0;
map<int,int>vst;
int main() {
	n=Get_Int();
	m=Get_Int();
	Start=Get_Int();
	End=Get_Int();
	if(!vst.count(Start))vst[Start]=++step;
	if(!vst.count(End))vst[End]=++step;
	Matrix G(m,m);
	for(int i=1; i<=m; i++) {
		int v=Get_Int(),x=Get_Int(),y=Get_Int();
		if(!vst.count(x))vst[x]=++step;
		if(!vst.count(y))vst[y]=++step;
		G[vst[x]][vst[y]]=G[vst[y]][vst[x]]=v;
	}
	G=G^n;
	printf("%lld\n",G[vst[Start]][vst[End]]);
	return 0;
}