题目描述
七夕夜游,走在SH街头,小w被这个城市晚上的繁华所震撼。
正当他在街边仰望周围的一对对时,一只喜鹊落在了他的肩上。
于是小w开始向喜鹊开始抱怨……
经过向喜鹊打听,小w了解到喜鹊们将SH分成了 N 片神奇的区域,只要从任意一个区域开始,
沿着特定的路线去访问恰好 K - 1 个区域(加上一开始的也就是总计到达过 K 个区域),
边走边许愿。那么在到达第 K 个区域时,就可以实现自己许下的这一个愿望。
小w当然迫不及待的想实现愿望,所以他给了你喜鹊留下的区域地图,要求你告诉他从任意一
个区域开始,任意一个区域结束,完成一次许愿所需要的最短时间。以便他做出最好的决策。
数据范围:
对于30%的数据: 1<=N,K<=10
对于50%的数据: 1<=N, K<= 50
对于100%的数据:N <= 50, K <= 1000000
输入数据中的所有时间不会超过 10^8。
输入格式
第一行两个数 N、K。
后接 N 行每行 N 个数,第 i 行 j 列的数 aij 表示从第 i 片区域走到第 j 片区域所需的
时间为 aij。如果从第 i 片区域走不到第 j 片区域,则 aij = -1。
输出格式
N 行每行 N 个数,第 i 行 j 列的数表示第 i 片区域开始、第 j 片区域结束的所需
最短时间。
样例输入
样例输出