题目

春天到了, HDU校园里开满了花, 姹紫嫣红, 非常美丽. 葱头是个爱花的人, 看着校花校草竞相开放, 漫步校园, 心情也变得舒畅. 为了多看看这迷人的校园, 葱头决定, 每次上课都走不同的路线去教室, 但是由于时间问题, 每次只能经过k个地方, 比方说, 这次葱头决定经过2个地方, 那他可以先去问鼎广场看看喷泉, 再去教室, 也可以先到体育场跑几圈, 再到教室. 他非常想知道, 从A点恰好经过k个点到达B点的方案数, 当然这个数有可能非常大, 所以你只要输出它模上1000的余数就可以了. 你能帮帮他么?? 你可决定了葱头一天能看多少校花哦

输入格式

输入数据有多组, 每组的第一行是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的时候输入结束

输出格式

计算每次询问的方案数, 由于走法很多, 输出其对1000取模的结果

输入样例

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

输出格式

2
0
1
3

分析

把给定的图转为邻接矩阵，即A(i,j)=1当且仅当存在一条边i->j。令C=AA，那么C(i,j)=ΣA(i,k)A(k,j)，实际上就等于从点i到点j恰好经过2条边的路径数（枚举k为中转点）。类似地，C*A的第i行第j列就表示从i到j经过3条边的路径数。同理，如果要求经过k步的路径数，我们只需要二分求出A^k即可。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<iomanip>
const int Inf = 0x3f3f3f3f;
using namespace std;
 
const int maxn=20+10;
const int mod=1000;
int s[maxn][maxn],sum[maxn][maxn],array[maxn][maxn];
int n,m;
 
void MatrixMult(int a[maxn][maxn],int b[maxn][maxn]){
    int c[maxn][maxn]={0};
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j){
            for(int k=0;k<n;++k){
                c[i][j]=(c[i][j]+a[i][k]*b[k][j])%mod;
            }
        }
    }
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j)a[i][j]=c[i][j];
    }
}
 
int Matrix(int a,int b,int k){
    for(int i=0;i<n;++i){ 
        for(int j=0;j<n;++j){
            if(i == j)sum[i][j]=1;
            else sum[i][j]=0;
        }
    }
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j)array[i][j]=s[i][j];
    }
    while(k){
        if(k&1)MatrixMult(sum,array);
        MatrixMult(array,array);
        k>>=1;
    }
    return sum[a][b];
}
 
int main(){
    int a,b,t,k;
    while(cin>>n>>m,n+m){
        memset(s,0,sizeof s);
        for(int i=0;i<m;++i){
            scanf("%d%d",&a,&b);
            s[a][b]=1;
        }
        cin>>t;
        while(t--){
            scanf("%d%d%d",&a,&b,&k);
            printf("%d\n",Matrix(a,b,k));
        }
    }
    return 0;
}