最短路+有向图找环
#include<cstdio> #include<iostream> #include<cstring> #include<queue> using namespace std; const int INF=0x3f3f3f3f; const int N=220; const int M=N*N*N; struct Edge{ int v,next; Edge(){} Edge(int v,int next):v(v),next(next){} }e[M*2]; int head[N*N],total; void init(){ memset(head,-1,sizeof(head));total=0; } void adde(int u,int v){ e[total]=Edge(v,head[u]);head[u]=total++; } int mp[N][N]; int dis[N*N]; queue<int> qq; int sou(int s,int t){ memset(dis,0x3f,sizeof(dis)); dis[mp[s][t]]=0; qq.push(mp[s][t]); while(!qq.empty()){ int u=qq.front();qq.pop(); for(int i=head[u];i!=-1;i=e[i].next){ int v=e[i].v; if(dis[v]>dis[u]+1){ dis[v]=dis[u]+1; qq.push(v); } } } return dis[mp[0][0]]<INF; } int vis[N*N]; void sou1(int s,int t){ memset(dis,0,sizeof(dis)); memset(vis,0,sizeof(vis)); dis[mp[s][t]]=0;vis[mp[s][t]]=1; qq.push(mp[s][t]); while(!qq.empty()){ int u=qq.front();qq.pop(); vis[u]=0; for(int i=head[u];i!=-1;i=e[i].next){ int v=e[i].v; if(dis[v]<dis[u]+1){ dis[v]=dis[u]+1; if(!vis[v]){ vis[v]=1;qq.push(v); } } } } } int dfs(int u){ vis[u]=2; for(int i=head[u];i!=-1;i=e[i].next){ int v=e[i].v; if(vis[v]){ if(vis[v]==2)return 1; } else if(dfs(v)){ return 1; } } vis[u]=1; return 0; } int H,T,R,cnt; int fun(int i,int j,int ii,int jj){ //printf("%d %d %d %d\n",i,j,ii,jj); if(ii+jj>R){ adde(mp[i][j],cnt); } else { adde(mp[i][j],mp[ii][jj]); } } int aa[N*2],bb[N*2]; int main(){ #ifdef DouBi freopen("in.cpp","r",stdin); #endif // DouBI while(scanf("%d%d%d",&H,&T,&R)!=EOF){ int n;scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d%d",&aa[i],&bb[i]); } int m;scanf("%d",&m); for(int i=1;i<=m;i++){ scanf("%d%d",&aa[i+n],&bb[i+n]); } cnt=0; for(int i=0;i<=R;i++){ for(int j=0;j<=R-i;j++){ mp[i][j]=cnt++; } } init(); for(int i=0;i<=R;i++){ for(int j=0;j<=R-i;j++){ for(int k=1;k<=n&&k<=i;k++){ int ii=i-k+aa[k],jj=j+bb[k]; fun(i,j,ii,jj); } for(int k=1;k<=m&&k<=j;k++){ int ii=i+aa[n+k],jj=j-k+bb[n+k]; fun(i,j,ii,jj); } } } if(sou(H,T)){ printf("Ivan\n"); printf("%d\n",dis[mp[0][0]]); continue; } memset(vis,0,sizeof(vis)); if(dfs(mp[H][T])){ printf("Draw\n"); continue; } sou1(H,T); printf("Zmey\n"); printf("%d\n",dis[cnt]); } return 0; }