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