2018.11.09【BZOJ1706】relays 奶牛接力跑（矩阵快速幂优化DP）

传送门

---

解析：

首先如果我们已经求出一个矩阵AiA_iAi​表示走iii步两点之间的最短路，只要我们知道A1A_1A1​，我们可以知道Ai+1A_{i+1}Ai+1​ Ai+1,u,v=min⁡k{Ai,u,k+A1,k,v}A_{i+1,u,v}=\min_k\{A_{i,u,k}+A_{1,k,v}\}Ai+1,u,v​=kmin​{Ai,u,k​+A1,k,v​}

然后发现这个东西是满足结合律的，就矩阵快速幂优化一下转移就行了。

---

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define re register 
#define gc getchar
#define pc putchar
#define cs const

inline int getint(){
	re int num;
	re char c;
	while(!isdigit(c=gc()));num=c^48;
	while(isdigit(c=gc()))num=(num<<1)+(num<<3)+(c^48);
	return num;
}

cs int N=101;
int n;
struct matrix{
	int a[N][N];
	matrix(){memset(a,0x3f,sizeof a);}
	void ori(){for(int re i=1;i<=n;++i)a[i][i]=0;}
	friend matrix operator*(cs matrix &A,cs matrix &B){
		matrix C;
		for(int re i=1;i<=n;++i)
		for(int re j=1;j<=n;++j)
		for(int re k=1;k<=n;++k)
		C.a[i][k]=min(C.a[i][k],A.a[i][j]+B.a[j][k]);
		return C;
	}
}A;

matrix quickpow(matrix a,int b){
	matrix ans;
	ans.ori();
	while(b){
		if(b&1)ans=ans*a;
		a=a*a;
		b>>=1;
	}
	return ans;
}

int id[1003];
int k,S,T,m;
signed main(){
	k=getint();
	m=getint();
	S=getint();
	T=getint();
	for(int re i=1;i<=m;++i){
		int w=getint(),u=getint(),v=getint();
		if(!id[u])id[u]=++n;
		if(!id[v])id[v]=++n;
		A.a[id[u]][id[v]]=A.a[id[v]][id[u]]=min(A.a[id[u]][id[v]],w);
	}
	printf("%d",quickpow(A,k).a[id[S]][id[T]]);
	return 0;
}