找过k条边的路径个数。
首先注意一下题意，同一个点过两次算两次，做过类似的，过k条边的最短路，只要搞一个矩阵，然后快速幂就好了，这个也一样，维护信息变一下，然后就好了。
如果k很大：
并不影响此种做法。
如果n很大：
改成dp。dp[x][k]表示过k个边到点x的路径数，然后就可以了。
代码：
#include <cstdio> #include <cstring> #include <string> using namespace std; const int maxn=100+10; const int maxm=20+10; int ed[maxm][maxm]; int n; struct JZ{ int a[maxm][maxm]; JZ(){ memset(a,0,sizeof(a)); } JZ(int s){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=ed[i][j]; } JZ(int s,int k){ memset(a,0,sizeof(a)); for(int i=1;i<=n;i++) a[i][i]=1; } friend JZ operator + (JZ a,JZ b){ JZ c; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++){ c.a[i][j]+=b.a[i][k]*a.a[k][j]; c.a[i][j]%=1000; } return c; } }; int ha[maxn]; int main(){ int N,m; while(~scanf("%d%d",&n,&m)&&(m||n)){ memset(ed,0,sizeof(ed)); int js1,js2; for(int i=1;i<=m;i++){ scanf("%d%d",&js1,&js2); ed[js1+1][js2+1]=1; } int q; scanf("%d",&q); for(int i=1;i<=q;i++){ scanf("%d%d%d",&js1,&js2,&N); bool f=1; JZ D(1,1); for(JZ now(1);N;now=now+now){ if(N&1) D=D+now; N>>=1; } printf("%d\n",D.a[js1+1][js2+1]); } } return 0; }
原文：https://www.cnblogs.com/wish-all-ac/p/12909812.html