← 返回题目列表

AtCoder · past17_l

L. 折扣券

中文机器翻译题面 查看原题

问题陈述

有 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