| 题目名称 | 598. 空中楼阁 |
|---|---|
| 输入输出 | house.in/out |
| 难度等级 | ★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 mouse
于2011-10-11加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：12， 提交：46， 通过率：26.09% | ||||
 HouJikan |
100 | 0.024 s | 0.44 MiB | C++ |
 OIdiot |
100 | 0.027 s | 0.51 MiB | C++ |
 donny |
100 | 0.048 s | 4.18 MiB | C++ |
 Truth.Cirno |
100 | 0.050 s | 0.38 MiB | C++ |
|
Truth.Cirno |
100 | 0.050 s | 0.38 MiB | C++ |
 lizhe |
100 | 0.052 s | 7.87 MiB | Pascal |
 Czb。 |
100 | 0.059 s | 3.12 MiB | C++ |
|
sywgz |
100 | 0.064 s | 0.89 MiB | C++ |
 kaaala |
100 | 0.072 s | 0.27 MiB | C++ |
 苏轼 |
100 | 0.077 s | 0.29 MiB | C++ |
| 本题关联比赛 | |||
| 20111012 | |||
| 关于 空中楼阁 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
残念啊，做的boolean[时间][地点]标记数组“时间”下标通通少加了“1”s，错三组……
| ||||
【问题描述】
话说 Z4 阴差阳错地来到了神秘岛。不久，他们发现，这是一个由 n 个小岛和一个中心岛组成的群岛，群岛之间有 m 座桥。令他们感到惊讶的是，这些桥并不是固定不变的，经较长时间的观察，发现它们会随时间作周期性的变化（即桥的两端会不断更换）。
话说 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 。
输入文件 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! ”。
输出文件 house .out 仅有一个整数，表示 Z4 最少得花多少时间到达中心岛。如果 Z4 无法到达中心岛，则输出“ Poor Z4! ”。
【输入输出样例1】
输入：
house.in
4 5 2
1 2
1 3
1 4
2 0
4 0
输入：
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
1 3
2 3
4 3
3 0
输出：
house.out
2
house.out
2
【输入输出样例2】
输入：
house.in
7 3 2
1 2
1 4
6 0
输入：
house.in
7 3 2
1 2
1 4
6 0
2 5
3 6
4 7
3 6
4 7
输出：
house.out
Poor Z4!