P1024 列车线路
列车线路
终于,卡卡西来到了一个叫“比特兰”的国家,“比特兰”是个很发达的国家,
有着非常高科技的列车,和非常复杂的列车线路。具体来说,从理论上,我们可
以假设这个国家的高科技列车可以不消耗时间的从 A 地瞬间转移到 B 地。同时,
铁路线路复杂到,每对城市之间都有列车连接。但是不幸的是,由于这种列车运
行需要很多维护工作,所以每天只能发出一次。从 i 到 j 的列车(i≠j)会在 ti,j
时间发出(保证 ti,j两两不同)。
如果有一条路径链接 A 和 B 两个城市,并且满足路径上的每⼀条边的发车时
间单调递增(也就是说经过的每段铁路的发出时间都要大于上一段的,因为我们
需要从上一段铁路换乘下一段铁路)。 现在“比特兰”的铁路局想要知道,一天
之内,对于每一对 i 和 j,如果想要从 i 到达 j,最早多早能到达呢?
输入:
第一行一个整数 n。
接下来 n 行,每行 n 个整数。表示 ti,j。(i=j 时保证 ti,j=0,不算一条线路)
输出:
n 行,每行 n 个整数 ansi,j,表示从 i 到 j 最早的到达时间。(i=j 的时候
ansi,j=0)
样例
输入: train.in
3
0 4 5
2 0 3
1 6 0
输出: train.out
0 4 5
2 0 3
1 4 0
数据范围:
对于 20%的数据, n<=10
对于 40%的数据, n<=20
对于 60%的数据, n<=50
对于 100%的数据, n<=500, ti,j<=109
信息
- 难度
- 9
- 分类
- (无)
- 标签
- 递交数
- 16
- 已通过
- 1
- 通过率
- 6%
- 上传者