首页 > 代码库 > [BZOJ 1297][SCOI 2009]迷路(矩阵快速幂)

[BZOJ 1297][SCOI 2009]迷路(矩阵快速幂)

题目:http://www.lydsy.com:808/JudgeOnline/problem.php?id=1297

分析:如果每条边的边权都是1,那么就相当于对邻接矩阵自乘T次(因为写一下递推式子f[i][j]=∑f[i][k]*f[k][j]等价于矩阵乘法的定义)。但是这题每条边的边权是1~9。

所以可以把每个点i拆成9个点形成链状:i9->i8->i7->i6->i5->i4->i3->i2->i1 (这条链中每条边的长度都为1)

然后对于原图中的 i->j边权为k的边 则可以表示为 i1->jk边权为1的边

然后对于新图的邻接矩阵快速幂自乘就可以了

[BZOJ 1297][SCOI 2009]迷路(矩阵快速幂)