Input输入数据有多组, 每组的第一行是2个整数 n, m(0 < n <= 20, m <= 100) 表示校园内共有n个点, 为了方便起见, 点从0到n-1编号,接着有m行, 每行有两个整数 s, t (0<=s,t<n) 表示从s点能到t点, 注意图是有向的.接着的一行是两个整数T,表示有T组询问(1<=T<=100),
接下来的T行, 每行有三个整数 A, B, k, 表示问你从A 点到 B点恰好经过k个点的方案数 (k < 20), 可以走重复边。如果不存在这样的走法, 则输出0
当n, m都为0的时候输入结束
Output计算每次询问的方案数, 由于走法很多, 输出其对1000取模的结果Sample Input
4 4
0 1
0 2
1 3
2 3
2
0 3 2
0 3 3
3 6
0 1
1 0
0 2
2 0
1 2
2 1
2
1 2 1
0 1 3
0 0
Sample Output
2
0
1
3
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<memory>
using namespace std;
const int maxn=31;
const int Mod=1000;
int n;
struct mat
{
int m[maxn][maxn];
mat(){memset(m,0,sizeof(m));}
mat friend operator*(mat a,mat b){
mat d;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
for(int k=0;k<n;k++)
d.m[i][j]=(d.m[i][j]+a.m[i][k]*b.m[k][j])%Mod;
return d;
}
mat friend operator^(mat a,int k){
mat d;
for(int i=0;i<n;i++) d.m[i][i]=1;
while(k){
if(k&1) d=d*a;
a=a*a;
k>>=1;
}
return d;
}
};
int main()
{
int m,k,i,x,y,q;
while(~scanf("%d%d",&n,&m)){
if(m==0&&n==0) return 0;
mat Map;
for(i=0;i<m;i++){
scanf("%d%d",&x,&y);
Map.m[x][y]=1;
}
scanf("%d",&q);
for(i=0;i<q;i++){
scanf("%d%d%d",&x,&y,&k);
mat ans;
ans=Map^k;
printf("%d\n",ans.m[x][y]);
}
}
return 0;
}
原文：http://www.cnblogs.com/hua-dong/p/7749902.html