记录编号	28595	评测结果	AAAAAAAAAA
题目名称	空中楼阁	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.112 s
提交时间	2011-10-16 08:45:06	内存使用	0.89 MiB

#include <cstdio>
const int MAXN = 81, MAXT = 10, INF = 1<<16;
int n, m, t, s, a, b, min, d[MAXN][MAXT];
bool G[MAXN][MAXT][MAXN][MAXT]; //G[a][t1][b][t2] <a-t1~t2-b>
bool F[MAXN][MAXT];
int main() {
    freopen("house.in","r",stdin);
    freopen("house.out","w",stdout);
    scanf("%d %d %d", &n, &m, &t);
    for(int i=0; i<t; i++)
        for(int j=0; j<m; j++) {
            scanf("%d %d", &a, &b);
            G[a][i][b][(i+1)%t] = G[b][i][a][(i+1)%t] = true;
        }
    for(int i=0; i<=n; i++)
        for(int j=0; j<t; j++) {
            G[i][j][i][(j+1)%t] = true;
            d[i][j] = INF;
        }
    d[1][0] = 0;
    while(a != -1) {
        a = -1;
        min = INF;
        for(int i=0; i<=n; i++)
            for(int j=0; j<t; j++)
                if(!F[i][j] && d[i][j] < min)
                    min = d[a = i][b = j];
        if(a != -1) {
            F[a][b] = true;
            for(int i=0; i<=n; i++)
                for(int j=0; j<t; j++)
                    if(G[a][b][i][j] && d[a][b] + 1 < d[i][j])
                        d[i][j] = min + 1;
        }
    }
    s = d[0][0];
    for(int i=0; i<t; i++)
        if(s > d[0][i])
            s = d[0][i];
    if(s <= 0 || s >= INF)
        printf("Poor Z4!\n");
    else
        printf("%d\n", s);
    return 0;
}