题目名称 598. 空中楼阁
输入输出 house.in/out
难度等级 ★☆
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试数据 10
题目来源 Gravatarmouse 于2011-10-11加入
开放分组 全部用户
提交状态
分类标签
分享题解
通过:12, 提交:46, 通过率:26.09%
GravatarHouJikan 100 0.024 s 0.44 MiB C++
GravatarOIdiot 100 0.027 s 0.51 MiB C++
Gravatardonny 100 0.048 s 4.18 MiB C++
GravatarTruth.Cirno 100 0.050 s 0.38 MiB C++
GravatarTruth.Cirno 100 0.050 s 0.38 MiB C++
Gravatarlizhe 100 0.052 s 7.87 MiB Pascal
GravatarCzb。 100 0.059 s 3.12 MiB C++
Gravatarsywgz 100 0.064 s 0.89 MiB C++
Gravatarkaaala 100 0.072 s 0.27 MiB C++
Gravatar苏轼 100 0.077 s 0.29 MiB C++
本题关联比赛
20111012
关于 空中楼阁 的近10条评论(全部评论)
残念啊,做的boolean[时间][地点]标记数组“时间”下标通通少加了“1”s,错三组……
GravatarTruth.Cirno
2011-10-17 14:18 1楼

598. 空中楼阁

★☆   输入文件:house.in   输出文件:house.out   简单对比
时间限制:1 s   内存限制:128 MiB
【问题描述】
    
话说 Z4 阴差阳错地来到了神秘岛。不久,他们发现,这是一个由 n 个小岛和一个中心岛组成的群岛,群岛之间有 m 座桥。令他们感到惊讶的是,这些桥并不是固定不变的,经较长时间的观察,发现它们会随时间作周期性的变化(即桥的两端会不断更换)。
    立方很早就留意到远远的那个中心岛了。他发现岛的上空好像有一个很巨大的东西,但实在太远了,看不清楚。此时 jakrinchose 得意地从身上拿出一个超高倍数望远镜,好像很自豪的样子,因为他平时专门用来看美女的工具此时终于派得上用场了。
    “那是一间小屋!架在一棵好大好大的树上!”
    “ Terrific !我们也许可以暂时在那安顿,好用来遮风避雨!”
    于是他们便决定前往中心岛上的那间空中楼阁。 Z4 的懒惰是出了名的,他们当然希望越早到越好,那么,你能帮帮他们吗?
    为方便计算,Z4 把小岛按 1..n 编号, 0 表示中心岛。 Z4 一开始在编号为 1 的小岛上。在岛上行走的时间忽略不计,过桥的时间为 1 个单位。岛上的桥变化的周期为 T ,在 nT+i(n=0,1,2,…;i=1,2,…,T) 时刻岛上的桥为第 i 种状态,一开始的时刻为 1 。两个小岛间可能有多条桥相连。在任一时刻, Z4 可以选择过桥,也可以原地不动。当然,如果无桥可过, Z4 只能在原地等待。
【输入格式】
    输入文件 house.in 的第一行包括三个整数 n ( 1 <=n<=80 ) , m(1<=m<=10000) 和 T(1<=T<=10) ,分别表示小岛的个数,岛上桥的数量和桥改变的周期 T 。
    接下来分别描述第 1..T 种状态,每种状态有 m 行,每行有两个整数 a, b ( 0<=a,b<=n ),表示这种状态时小岛 a 和 b 有一条桥相连。两状态之间用一空行隔开。
【输出格式】
    输出文件 house .out 仅有一个整数,表示 Z4 最少得花多少时间到达中心岛。如果 Z4 无法到达中心岛,则输出“ Poor Z4! ”。
【输入输出样例1】
 
输入:
house.in
4 5 2
1 2
1 3
1 4
2 0
4 0
1 3
1 3
2 3
4 3
3 0
输出:
house.out
2
【输入输出样例2】
 
输入:
house.in
7 3 2
1 2
1 4
6 0
2 5
3 6
4 7

输出:
house.out
Poor Z4!