中文题就不说题意了，其中 i 到 j 经过k个点的所有方案就是两个邻接矩阵相乘k-1次之后的结果。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
using namespace std;
const int mo = 1000;
int n,m;
struct node{int m[31][31];node(){memset(m,0,sizeof(m));}};node cmp(node a, node b){node te;for(int i = 0; i < n; i++)for(int j = 0; j < n; j++){te.m[i][j]=0;for(int k = 0; k< n; k++){te.m[i][j] += a.m[i][k] * b.m[k][j]; te.m[i][j] %= mo; }} return te;
}node powermod(node base,int k,int a,int b){node ans;for(int i = 0; i <n; i++ )ans.m[i][i] = 1;while(k){if(k&1) ans = cmp(ans, base);k >>= 1;base=cmp(base, base);}cout<<ans.m[a][b]<<endl;return ans;}int main(){int a,b,T,k;while(scanf("%d%d",&n,&m)&&(n || m)){node te;//这个定义在while函数外，导致wa while(m--){scanf("%d%d",&a,&b);te.m[a][b] = 1;}scanf("%d",&T);while(T--){scanf("%d%d%d",&a,&b,&k);powermod(te,k,a,b); }}return 0;
}