题目链接：

题意：

 对于给定的一个矩阵A，A+A^2+A^3+...+A^K 是多少呢？

其中A^2 表示两个矩阵的乘积A*A，A^3表示三个矩阵的乘积A*A*A，依此类推。

求结果中的非0元素个数。

题解：

乍一看，还以为要矩阵快速幂+矩阵等比求和呢，然后一看范围，卧槽，没法搞啊。

然后我们可以考虑一下这题的特殊性。

只求非0的元素个数。

对于mat[i][j]不为0必须存在一个k使得mat[i][k]*mat[k][j]!=0就行。

所以我们可以对每个点用BFS去求能到达的位置，然后对于k，因为k是大于N的，

i到j最多会经历N-1个点，所以k也不用处理。

分析完后其实就是一个简单的BFS。

1 #include
      
        2 #define F(i,a,b) for(int i=a;i<=b;++i) 3 using namespace std; 4  5 const int N=10007; 6 int g[N],v[N],nxt[N],ed,n,m,d[N],Q[N]; 7 char k[N]; 8  9 void adg(int x,int y){v[++ed]=y,nxt[ed]=g[x],g[x]=ed;}10 11 int sum(int s)12 {13     int l=1,r=0,ret=0;14     F(i,1,n)d[i]=0;15     Q[++r]=s,d[s]=1;16     while(l<=r)17     {18         int x=Q[l++];19         for(int i=g[x];i;i=nxt[i])20         {21             if(d[v[i]])continue;22             d[v[i]]=1,Q[++r]=v[i];23         }24     }25     F(i,1,n)ret+=d[i];26     return ret;27 }28 29 int main()30 {31     while(~scanf("%d%d%s",&n,&m,k))32     {33         memset(g,0,sizeof(g)),ed=0;34         F(i,1,m)35         {36             int x,y,z;37             scanf("%d%d%d",&x,&y,&z);38             adg(x+1,y+1);39         }40         int ans=0;41         F(i,1,n)ans+=sum(i);42         printf("%d\n",ans);43     }44     return 0;45 }