比赛 |
2024暑假C班集训D |
评测结果 |
AAAAAEEEEE |
题目名称 |
沼泽鳄鱼 |
最终得分 |
50 |
用户昵称 |
健康铀 |
运行时间 |
1.327 s |
代码语言 |
C++ |
内存使用 |
5.71 MiB |
提交时间 |
2024-07-13 10:40:27 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
int n,m,s,t,nf,mod=10000;
long long k;
long long f[55][2005];
struct abc
{
vector<int> q;
};
vector<abc> v(65);
struct fish{
int t;
vector<int> ans;
};
vector<fish> g(55);
inline int dfs(int x, int ti){
if(ti>k)
return 0;
if(f[x][ti]!=-1)
return f[x][ti];
for(int i=1;i<=nf;++i)
if(g[i].ans[ti%g[i].t]==x)
return f[x][ti]=0;
if(x == t && ti == k)
return f[x][ti]=1;
long long ans=0;
for(int i=0; i<v[x].q.size(); ++i)
ans=(ans+dfs(v[x].q[i],ti+1))%mod;
return f[x][ti] = ans;
}
int main()
{
freopen("swamp.in", "r", stdin);
freopen("swamp.out", "w", stdout);
memset(f,-1,sizeof(f));
cin >> n >> m >> s >> t >> k;
for(int i = 1; i <= m; ++i)
{
int x, y;
cin >> x >> y;
v[x].q.push_back(y);
v[y].q.push_back(x);
}
cin>>nf;
for(int i=1;i<=nf;++i){
cin >> g[i].t;
for(int j = 1; j <= g[i].t; ++j)
{
int p;
cin >> p;
g[i].ans.push_back(p);
}
}
cout << dfs(s,0);
return 0;
}