欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-22 11:40:51
...

传送门


解析:

首先如果我们已经求出一个矩阵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;
}