PID559 / 七夕夜游
题目描述

七夕夜游,走在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 片区域结束的所需

最短时间。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论