#884. 奇怪的电梯

奇怪的电梯

样例下载

【题目描述】

小明是一个旅游爱好者,这次他来到了一座新的城市。

城市中央有一幢高耸入云的大楼。这幢楼到底有多少层呢?据说和非负整数的个数是一样多的。

小明想爬上这座大楼来观赏新城市的全景。这幢大楼的楼层从下至上用从小到大的非负整数编号。每层楼有 nn 个房间,用 11 到 nn 的正整数编号。楼层之间用电梯连接,电梯只能上行,不能下行或者同层移动。电梯用 (u,v,w)(u,v,w) 的形式给出,表示对于任意整数 ii,由第 ii 层的房间 uu 到第 i+wi+w 层的房间 vv 有一部电梯。电梯只能从起点开往终点,不能中途停留。

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

【输入】

第一行包含一个正整数 TT,表示数据的组数。

接下来的数据分为 TT 个部分。每个部分:

  • 第一行包含两个正整数 nn 和 mm,意义见题目描述。
  • 接下来 nn 行,每行包含 nn 个非负整数。这 nn 行中,第 ii 行第 jj 个数为 Wi,jW_{i,j},如果 Wi,jW_{i,j} 非零,则表示有电梯 (i,j,Wi,j)(i,j,W_{i,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

【样例说明】

第一组数据中,依次到达的房间顺序为:0层1号 → 1层2号 → 2层3号 → 22层1号 → 23层2号 → 24层3号 → 44层1号 → 94层4号 → 144层6号 → 147层6号;

第二组数据中,依次到达的房间顺序为:0层1号 → 1层2号 → 2层3号 → 22层1号 → 23层2号 → 24层3号 → 44层1号 → 94层4号 → 95层5号 → 103层4号 → 153层6号。第二组数据最后到达了153层,但是没有更少的乘坐电梯次数使得恰好到达152层,因此答案为10。

【数据范围】

1、有10%的数据所有的 n=2n=2;

2、有20%的数据 m≤3000m≤3000;

3、有20%的数据对于满足 1≤i,j≤n1≤i,j≤n 的整数 ii 和 jj,若 Wi,j≠0W_{i,j}≠0,则有 Wi,j≥1015W_{i,j}≥10^{15};

4、有30%的数据所有的 n=40n=40。

以上各类数据均不包含其他类数据。对于所有数据 T=5,1≤n≤100,1≤m≤1018T=5,1≤n≤100,1≤m≤10^{18};对于满足 1≤i,j≤n1≤i,j≤n 的整数ii 和 jj,有 0≤Wi,j≤10180≤W_{i,j}≤10^{18}。数据保证能够到达 mm 层或更高的楼层。