OpenJudge

1053:[陈许旻]大楼

总时间限制:
400000ms
单个测试点时间限制:
20000ms
内存限制:
262144kB
描述

    xz是一个旅游爱好者,这次他来到了一座新的城市。城市中央有一幢高耸入云的大楼。这幢楼到底有多少层呢?据说和非负整数的个数是一样多的。xz想爬上这座大楼来观赏新城市的全景。

    这幢大楼的楼层从下至上用从小到大的非负整数编号。每层楼有n个房间,用1n的正整数编号。楼层之间用电梯连接,电梯只能上行,不能下行或者同层移动。(下楼一般自行解决)电梯用(u,v,w)的形式给出,表示对于任意正整数i,有第i层的房间u到第i+w层的房间v有一部电梯。电梯只能从起点开往终点,不能中途停留。

    xz想要观赏城市全景,至少需要登上第m层楼,即最终需要到达的楼层数≥m。由于乘坐电梯要缴纳高额的费用,而如果花销太大回家就没法报账了,xz希望乘坐电梯的次数最少。现在xz在第0层的1号房间,你需要求出这个最少的乘坐次数。

输入
第一行包含一个正整数T,表示数据的组数。接下来的数据分为T个部分。
每个部分第一行包含两个正整数n和m,意义见题目描述。
接下来n行,每行包含n个非负整数。这n行中,第i行第j个数为wi,j,如果wi,j非零,则表示有电梯(i,j,wi,j)。
同一行各个数之间均用一个空格隔开。
输出
对于每组数据,输出一行一个正整数,最少的乘坐次数。
样例输入
2
6 147
0 1 0 50 0 0
0 0 1 0 0 0
20 0 0 0 0 0
0 0 0 0 1 50
0 0 0 8 0 0
0 0 0 0 0 3
6 152
0 1 0 50 0 0
0 0 1 0 0 0
20 0 0 0 0 0
0 0 0 0 1 50
0 0 0 8 0 0
0 0 0 0 0 3
样例输出
9
10
提示
有如下几类具有特点的数据:
1、有10%的数据所有的n=2;
2、有20%的数据m≤3000;
3、有20%的数据对于满足1≤i,j≤n的整数i和j,若wi,j≠0,则有wi,j≥1015;
4、有30%的数据所有的n=40。
以上各类数据均不包含其他类数据。
对于所有数据T=5,1≤n≤100,1≤m≤1018;对于满足1≤i,j≤n的整数i和j,有0≤wi,j≤1018。
数据保证能够到达m层或更高的楼层。
全局题号
4815
添加于
2012-05-20
提交次数
1
尝试人数
1
通过人数
1