比赛 2024暑假C班集训D 评测结果 AAAAAEEEEE
题目名称 沼泽鳄鱼 最终得分 50
用户昵称 liuyiche 运行时间 1.215 s
代码语言 C++ 内存使用 5.71 MiB
提交时间 2024-07-13 09:14:01
显示代码纯文本
#include <bits/stdc++.h>
            
using namespace std;

typedef long long ll;

int n, m, s, t, nf;
int mod = 10000;
ll k; 
ll f[55][2005];

struct node
{
    vector<int> nxt;
};
vector<node> v(55);

struct fish
{
    int t;
    vector<int> re;
};
vector<fish> g(55);

inline int dfs(int x, int time)
{
    if(time > k)
        return 0;
    if(f[x][time] != -1)
        return f[x][time];
    for(int i = 1; i <= nf; ++i)
        if(g[i].re[time%g[i].t] == x)
            return f[x][time] = 0;
    if(x == t && time == k)
        return f[x][time] = 1;
    ll ans = 0;
    for(int i = 0; i < v[x].nxt.size(); ++i)
        ans = (ans+dfs(v[x].nxt[i],time+1))%mod;
    return f[x][time] = ans;
}
    
int main()
{
    freopen("swamp.in", "r", stdin);
    freopen("swamp.out", "w", stdout);
        
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    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].nxt.push_back(y);
        v[y].nxt.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].re.push_back(p);
        }
    }
    cout << dfs(s,0);
    
   	return 0;
}