问题陈述
有 N 城市编号 1 通过 N.
每对不同的城市都通过双向收费公路连接。有一张优惠券可以在任何道路上使用以获得通行费折扣。
城市间道路收费 i 和城市 j (i \lt j) is a_{i,j} 日元;有了优惠券,就是 b_{i,j} 日元。 (b_{i,j} \lt a_{i,j})
查找所有城市对的以下值 (i, j) 这样 i \lt j:
- 从城市出发所需的最低金额 i 前往城市 j,优惠券累计最多使用一次。
约束
- 2 \leq N \leq 300
- 1 \leq b_{i,j} \lt a_{i,j} \leq 10^4 (i \lt j)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N
a_{1,2} a_{1,3} \dots a_{1,N}
a_{2,3} \dots a_{2,N}
\vdots
a_{N-1,N}
b_{1,2} b_{1,3} \dots b_{1,N}
b_{2,3} \dots b_{2,N}
\vdots
b_{N-1,N}
输出
按以下格式打印答案。在这里, c_{i,j} 表示从城市出发所需的最低金额 i 前往城市 j,最多使用一次优惠券。
c_{1,2} c_{1,3} \dots c_{1,N}
c_{2,3} \dots c_{2,N}
\vdots
c_{N-1,N}
示例输入 1
4 4 8 5 6 8 3 1 6 1 5 2 1
示例输出 1
1 4 1 5 2 1
例如,您可以从城市出发 1 前往城市 3 最多使用一次优惠券,总费用为 4 日元,这是最小值,如下:
- 从城市出发 1 前往城市 4 费用为 1 日元,使用优惠券。
- 从城市出发 4 前往城市 3 费用为 3 日元,无需使用优惠券。
示例输入 2
6 2255 36 196 3623 6579 681 183 473 8830 7549 743 8216 1078 9 224 105 3 1 810 15 7 125 11 3 50 6 1781 537 4 85
示例输出 2
43 3 1 42 10 7 12 11 3 37 6 46 94 4 85