给图，图中任意可达的两点间步数为1

问从图中A点走到B点步数为k的有几条路

 

祭出离散数学图论那章中的 邻接矩阵A.

设S=A^k

则 S[a][b] 为 a到b，步数为k的不同路的条数

剩下的就是矩阵快速幂了

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 const int mod=1000;  6 struct P{ 7     int a[20][20]; 8 };     9 int n,m,t,a,b,k;10 P s,c;11 P mult(P a,P b)12 {13     P c;14     memset(c.a,0,sizeof(c.a));15     for(int i=0;i
        
         >=1;37     }38 }39 int main()40 {41     while(~scanf("%d%d",&n,&m)&&(m+n))42     {43         memset(s.a,0,sizeof(s.a));44         for(int i=1;i<=m;i++)45         {46             scanf("%d%d",&a,&b);47             s.a[a][b]=1;48         }49         scanf("%d",&t);50         for(int i=1;i<=t;i++)51         {52             scanf("%d%d%d",&a,&b,&k);53             fuc(k,s);54             printf("%d\n",c.a[a][b]);55         }56     }57 }