n<=20个点m<=100条边有向图不带权，t个询问问Ai到Bi的经过k<=20条边方案数多少。
f[i][j]--i到j的方案数，
，初始化成初邻接矩阵，这样做一次就得到2条路最短路，做两次就是4条……这东西不就是矩乘吗？
1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 #include<algorithm> 5 //#include<iostream> 6 using namespace std; 7 8 int n,m,t; 9 #define maxn 23 10 typedef int mat[maxn][maxn]; 11 mat a,ans; 12 const int mod=1000; 13 void copy(mat a,mat b) 14 { 15 for (int i=1;i<=n;i++) 16 for (int j=1;j<=n;j++) 17 a[i][j]=b[i][j]; 18 } 19 void mul(mat a,mat b,mat ans) 20 { 21 mat t;memset(t,0,sizeof(t)); 22 for (int i=1;i<=n;i++) 23 for (int j=1;j<=n;j++) 24 for (int k=1;k<=n;k++) 25 t[i][j]=(t[i][j]+a[i][k]*b[k][j]%mod)%mod; 26 copy(ans,t); 27 } 28 void init(mat t) 29 { 30 memset(t,0,sizeof(mat)); 31 for (int i=1;i<=n;i++) t[i][i]=1; 32 } 33 void pow(mat a,int b,mat ans) 34 { 35 mat t,tmp;init(t);copy(tmp,a); 36 while (b) 37 { 38 if (b&1) mul(t,tmp,t); 39 mul(tmp,tmp,tmp); 40 b>>=1; 41 } 42 copy(ans,t); 43 } 44 int main() 45 { 46 while (scanf("%d%d",&n,&m),n||m) 47 { 48 int x,y,v;memset(a,0,sizeof(a)); 49 for (int i=1;i<=m;i++) 50 { 51 scanf("%d%d",&x,&y); 52 x++;y++; 53 a[x][y]=1; 54 } 55 scanf("%d",&t); 56 for (int i=1;i<=t;i++) 57 { 58 scanf("%d%d%d",&x,&y,&v); 59 x++;y++; 60 pow(a,v,ans); 61 printf("%d ",ans[x][y]); 62 } 63 } 64 return 0; 65 }