记录编号 590934 评测结果 AATTAMMMMM
题目名称 [ZJOI 2005] 沼泽鳄鱼 最终得分 30
用户昵称 Gravatar123 是否通过 未通过
代码语言 C++ 运行时间 6.743 s
提交时间 2024-07-13 14:45:12 内存使用 131.38 MiB
显示代码纯文本
    #include <bits/stdc++.h>
    using namespace std;
    const int N=1010;
    int n,m,s,t,k,tot=0,head[N],nxt[N],idx[N],res[N],p[N][N],ans=0,e;
    void add(int x,int y)
    {
        idx[++tot]=y;
        nxt[tot]=head[x];
        head[x]=tot;
    }
    void dfs(int step,int now)
    {
        if (step==k+1)
        {
            if (now==t)
            {
                ans=(ans+1)%10000;
            }
            return ;
        }
        for (int i=head[now];i;i=nxt[i])
        {
            int y=idx[i],flag=1;
            for (int j=1;j<=e;j++)
            {
                if (p[j][step%res[j]]==y)
                {
                    flag=0;
                    break;
                }
            }
            if (flag)
            {
                dfs(step+1,y);
            }
        }
    }
    int main() {
        freopen("swamp.in","r",stdin);
        freopen("swamp.out","w",stdout);
        scanf("%d%d%d%d%d",&n,&m,&s,&t,&k);
        for (int i=1;i<=m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            add(x,y);
            add(y,x);
        }
        scanf("%d",&e);
        for (int i=1;i<=e;i++)
        {
            scanf("%d",&res[i]);
            for (int j=0;j<res[i];j++)
            {
                scanf("%d",&p[i][j]);
            } 
        }
        dfs(1,s);
        printf("%d",ans);
    }