本文共 1110 字，大约阅读时间需要 3 分钟。

非常$nb$的一道题

假如求方案数,那么可以定义$f[i][j]$为$i$次到$j$的方案数

可以得到$f[i+1][v]+=f[i][j]$

所以可以以01邻接矩阵作矩阵快速幂得到方案数.

然后这里的权值也是同样的道理

假如现在得到了经过$x$个点的最短路,求经过$x+y$个点的最短路

那么只需要有经过$y$个点的最短路即可

这样加起来就经过了$x+y$个点

所以把邻接矩阵同时作为初始矩阵和递推矩阵开始递推

#include 
   
    #include 
    
     #include 
     
      using namespace std;int f[1000009],id;struct matrix{
   	int m[209][209];	matrix(){
    memset(m,0x3f3f3f3f,sizeof m); }};matrix operator * (matrix a,matrix b){
   	matrix ans;	for(int k=1;k<=id;k++)	for(int i=1;i<=id;i++)	for(int j=1;j<=id;j++)		ans.m[i][j] = min( ans.m[i][j],a.m[i][k]+b.m[k][j] );	return ans;}matrix quick(matrix x,int n){
   	matrix ans = x;	while( n )	{
   		if( n&1 )	ans = ans*x;		n >>= 1;		x = x*x;	}	return ans;}int main(){
   	int n,t,s,e;	cin >> n >> t >> s >> e;	matrix ans;	for(int i=1;i<=t;i++)	{
   		int w,l,r; cin >> w >> l >> r;		if( !f[l] )	f[l] = ++id;		if( !f[r] )	f[r] = ++id;		ans.m[f[l]][f[r]] = ans.m[f[r]][f[l]] = min( ans.m[f[l]][f[r]],w );	}	ans = quick( ans,n-1 );	cout << ans.m[f[s]][f[e]];}
     
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/110007543 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！