比赛 2024暑假C班集训D 评测结果 AWWWETTTTT
题目名称 沼泽鳄鱼 最终得分 10
用户昵称 djyqjy 运行时间 10.429 s
代码语言 C++ 内存使用 3.30 MiB
提交时间 2024-07-13 11:48:40
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int N=55,M=1010,F=25,MOD=10000;
int n,m,s,e;
long long k;
int ver[2*M],nxt[2*M],hd[N];
int jsq;
void add(int x,int y)
{
    ver[++jsq]=y;
    nxt[jsq]=hd[x];
    hd[x]=jsq;
    return;
}
int nf;
struct fish
{
    int t;
    int p[5];
}fs[F];
int dp[N];
int mark[N];
int dpp[N];
void bfs()
{
    queue <pair<int,int> > q;
    dp[s]=1;
    q.push(make_pair(s,0));
    mark[s]=1;
    int last=0;
    while(1)
    {
        if(q.front().second==k) break;
        int x=q.front().first,d=q.front().second;
        q.pop();
        if(d!=last)
        {
            for(int i=0;i<n;i++)
                dp[i]=dpp[i];
        }
        last=d;
        mark[x]=0;
        for(int i=hd[x];i;i=nxt[i])
        {
            int y=ver[i];
            bool flag=1;
            for(int j=1;j<=nf;j++)
            {
                if(fs[j].p[(d+1)%fs[j].t]==y)
                {
                    flag=0;
                    break;
                }
            }
            if(!flag) continue;
            if(mark[y]) dpp[y]=(dp[y]+dp[x])%MOD;
            else q.push(make_pair(y,d+1)),mark[y]=1,dpp[y]=dp[x];
        }
    }
}
int main()
{
    freopen("swamp.in","r",stdin);
    freopen("swamp.out","w",stdout);
    scanf("%d%d%d%d%lld",&n,&m,&s,&e,&k);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    scanf("%d",&nf);
    for(int i=1;i<=nf;i++)
    {
        scanf("%d",&fs[i].t);
        for(int j=0;j<fs[i].t;j++)
            scanf("%d",&fs[i].p[j]);
    }
    bfs();
    printf("%d",max(dpp[e],dp[e]));
    return 0;
}