比赛 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;
}