1928: 最优乘车
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：5
Solved：2
Description
H城是一个旅游胜地，每年都有成千上万的人前来观光。为方便游客，巴士公司在各个旅游景点及宾馆，饭店等地都设置了巴士站并开通了一些单程巴上线路。每条单程巴士线路从某个巴士站出发，依次途经若干个巴士站，最终到达终点巴士站。
一名旅客最近到H城旅游，他很想去S公园游玩，但如果从他所在的饭店没有一路巴士可以直接到达S公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士, 这样换乘几次后到达S公园。
现在用整数1,2,…N 给H城的所有的巴士站编号，约定这名旅客所在饭店的巴士站编号为1，S公园巴士站的编号为N。
写一个程序，帮助这名旅客寻找一个最优乘车方案,使他在从饭店乘车到S公园的过程中换车的次数最少。
一名旅客最近到H城旅游，他很想去S公园游玩，但如果从他所在的饭店没有一路巴士可以直接到达S公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士, 这样换乘几次后到达S公园。
现在用整数1,2,…N 给H城的所有的巴士站编号，约定这名旅客所在饭店的巴士站编号为1，S公园巴士站的编号为N。
写一个程序，帮助这名旅客寻找一个最优乘车方案,使他在从饭店乘车到S公园的过程中换车的次数最少。
Input
第一行有两个数字M和N(1<=M<=100 1<N<=500），表示开通了M条单程巴士线路，总共有N个车站。从第二行到第M刊行依次给出了第1条到第M条巴士线路的信息。其中第i+1行给出的是第i条巴士线路的信息，从左至右按运行顺序依次给出了该线路上的所有站号相邻两个站号之间用一个空格隔开。
Output
只有一行。如果无法乘巴士从饭店到达S公园，则输出"NO"，否则输出你的程序所找到的最少换车次数，换车次数为0表示不需换车即可到达。
Sample Input Copy
3 7
6 7
4 7 3 6
2 1 3 5
Sample Output Copy
2HINT
此题可以换个思路去想，以样例为例，我们不考虑换乘的次数，设同一条线路上的任意两点间的距离为 1，同时不需要换乘，这时便可以惊奇的发现从 1（起点）跑到 n（终点）的最短路径 1 即为正确答案！这是为什么呢？其原因是当需要换乘时，肯定会从当前线路上走到任意一点再进行换乘，至于为什么肯定会从当前线路上走到另外一点自己去想（或者评论私信问），从而换乘的次数就便是在任意一条路径上走的次数了（走完之后肯定会去换乘，最后走的一次除外）。当然我们最后答案必须减一，其原因就是当走到最后一条（再也不会换乘了）线路时，直接走到终点是不花换成次数的，而我们却记录了一次，所以最后要减一。数据很小，用 Floyd实现就行了。
本题坑点：读入很坑，需要用字符串读入，还有记得把第一行行末空格给过滤掉，否则 getline或 gets 会把这个回车也给读了。
本题坑点：读入很坑，需要用字符串读入，还有记得把第一行行末空格给过滤掉，否则 getline或 gets 会把这个回车也给读了。