How many ways??
题目描述
春天到了, HDU校园里开满了花, 姹紫嫣红, 非常美丽. 葱头是个爱花的人, 看着校花校草竞相开放, 漫步校园, 心情也变得舒畅. 为了多看看这迷人的校园, 葱头决定, 每次上课都走不同的路线去教室, 但是由于时间问题, 每次只能经过$k$个地方, 比方说, 这次葱头决定经过$2$个地方, 那他可以先去问鼎广场看看喷泉, 再去教室, 也可以先到体育场跑几圈, 再到教室. 他非常想知道, 从A 点恰好经过$k$个点到达B点的方案数, 当然这个数有可能非常大, 所以你只要输出它模上$1000$的余数就可以了. 你能帮帮他么?? 你可决定了葱头一天能看多少校花哦
输入格式
输入数据有多组, 每组的第一行是$2$个整数$n$,$m$($0 < n \le 20$,$m \le 100$) 表示校园内共有$n$个点, 为了方便起见, 点从$0$到$n-1$编号,接着有$m$行, 每行有两个整数$s$,$t$($0 \le s$,$t<n$) 表示从$s$点能到$t$点, 注意图是有向的.接着的一行是两个整数$T$,表示有$T$组询问($1 \le T \le 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
题解
数据范围很小,直接暴力dp就能过。
$dp[i][j][k]$表示从$i$到$j$走了$k$个点的方案数,直接枚举边转移就好了。
注意:有多组数据
上代码:
#include<bits/stdc++.h>
#define mod 1000
using namespace std;
int n,m;
struct aa{
int to,nxt;
}p[109];
int h[109],len;
bool kk[29][29];
int x,y;
int t;
int a,b,k;
void add(int u,int v){
p[++len].to=v;
p[len].nxt=h[u];
h[u]=len;
}
int dp[29][29][29];
int main(){
while(1){
memset(dp,0,sizeof(dp));
memset(kk,0,sizeof(kk));
memset(h,0,sizeof(h));
scanf("%d%d",&n,&m);
if(n==0 && m==0) break;
len=0;
for(int j=1;j<=m;j++){
scanf("%d%d",&x,&y);
kk[x][y]=1;
}
for(int q=0;q<n;q++){
dp[q][q][0]=1;
for(int s=0;s<20;s++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(kk[i][j]){
dp[q][j][s+1]+=dp[q][i][s];
dp[q][j][s+1]%=mod;
}
}
}
}
}
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&a,&b,&k);
printf("%d\n",dp[a][b][k]);
}
}
return 0;
}