记录编号	36639	评测结果	AAAAAAAAAA
题目名称	空中楼阁	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.077 s
提交时间	2012-03-15 20:14:00	内存使用	2.78 MiB

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define readfile(str) freopen(str,"r",stdin)
#define writefile(str) freopen(str,"w",stdout)
#define MAXN 811
#define MAX 1000000000

int N,M,T;
int Ans=MAX;
int Bridge[82][11];
int Map[MAXN][MAXN];
int Abut[MAXN];
int C;
int flag[MAXN];
int dist[MAXN];
	
inline int GetNextSt(int now)
{
	if(now<=T-1)
		return now+1;
	return 1;
}


void init()
{
	scanf("%d %d %d\n",&N,&M,&T);
	int p=0;
	int i,j;
	for (i=1;i<=N+1;i++)
		for (j=1;j<=T;j++)
			Bridge[i][j]=++p;
	C=N+1;
	
	
	int a,b;
	int x,y,tmp;
	for (i=1;i<=T;i++)
	{
		tmp=GetNextSt(i);
		for (j=1;j<=M;j++)
		{
			scanf("%d %d\n",&a,&b);
			if(a==0) a=C;
			if(b==0) b=C;
			
			x=Bridge[a][i];
			y=Bridge[b][tmp];
			Map[x][++Abut[x]]=y;
			
			x=Bridge[b][i];
			y=Bridge[a][tmp];
			Map[x][++Abut[x]]=y;
		} 
	}

	for (i=1;i<=N+1;i++)
	{
		for (j=1;j<=T;j++)
		{
			tmp=GetNextSt(j);
			x=Bridge[i][j];
			y=Bridge[i][tmp];
			Map[x][++Abut[x]]=y;
		}	
	}
	N=p;
}

int GetShortestPath()
{
	int S=1;

	int i,j;
	
	for (i=1;i<=N;i++)
	{
		dist[i]=MAX;
		flag[i]=0;
	}
	for (i=1;i<=Abut[S];i++)
		dist[Map[S][i]]=1;
	
	dist[S]=0;
	for (i=2;i<=N;i++)
	{
		int tmp=MAX;
		int u=S;
		for(j=1;j<=N;j++)
		{
			if(!flag[j] && dist[j]<tmp)
			{
				u=j;
				tmp=dist[j];
			}
		}
		flag[u]=1;
		
		for(j=1;j<=Abut[u];j++)
		{
			if(!flag[Map[u][j]])
			{
				int newdist=dist[u]+1;
				if(newdist<dist[Map[u][j]])
				{
					dist[Map[u][j]]=newdist;
				}
			}
		}
	}
	int Res=MAX;
	int x;
	for (i=1;i<=T;i++)
	{
		x=Bridge[C][i];
		if(dist[x]<Res)
			Res=dist[x];
	}
	return Res;
}

int main()
{
	readfile("house.in"),writefile("house.out");
	init();
	int Res=GetShortestPath();
	if(Res!=MAX)
		printf("%d\n",Res);
	else
		printf("Poor Z4!\n");
	return 0;
}