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
矩阵的k次方表示经过k次转移到达该点的路径次数
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<sstream> #include<algorithm> #include<queue> #include<deque> #include<iomanip> #include<vector> #include<cmath> #include<map> #include<stack> #include<set> #include<memory> #include<list> #include<string> #include<functional> using namespace std; typedef long long LL; typedef unsigned long long ULL; #define MAXN 29 #define L 31 #define INF 1000000009 #define eps 0.00000001 #define MOD 1000 int n, m; struct mat { mat() { memset(data, 0, sizeof(data)); } int data[MAXN][MAXN]; mat operator*(const mat& rhs) { mat ret; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (data[i][j]) { for (int k = 0; k < n; k++) ret.data[i][k] = (ret.data[i][k] + data[i][j] * rhs.data[j][k]) % MOD; } } } return ret; } }; mat fpow(mat a, int k) { mat tmp = a; mat ret; for (int i = 0; i < n; i++) ret.data[i][i] = 1; while (k) { if (k & 1) ret = tmp*ret; tmp = tmp*tmp; k /= 2; } return ret; } int main() { while (scanf("%d%d", &n, &m), n + m) { int f, t, d; mat M; for (int i = 0; i < m; i++) { scanf("%d%d", &f, &t); M.data[f][t] = 1; } int T; scanf("%d", &T); while (T--) { scanf("%d%d%d", &f, &t, &d); mat ans = fpow(M, d); printf("%d\n", ans.data[f][t]); } } }
原文：http://www.cnblogs.com/joeylee97/p/7395288.html