/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
問題文
1 から N までの番号がついた N 個の都市があります。
すべての相異なる都市同士の間には双方向に通行できる有料道路があります。また、すべての道路に使用できる割引券があり、これを使用すると通行料を安くすることができます。
都市 i と都市 j (i \lt j) を結ぶ道路の通行料は a_{i,j} 円で、割引券を使うと b_{i,j} 円になります。(b_{i,j} \lt a_{i,j})
i \lt j を満たすすべての都市の組 (i, j) に対して次の値を求めてください。
- 割引券を合計 1 回以下使用して都市 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} は 割引券を合計 1 回以下使用して都市 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 へ割引券を合計 1 回以下使用して移動する場合は、次のように移動すれば 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
Problem Statement
There are N cities numbered 1 through N.
Every pair of different cities is connected by a bidirectional toll road. There is a voucher that can be used on any road to get a discount on the toll.
The toll of the road between city i and city j (i \lt j) is a_{i,j} yen; with the voucher, it is b_{i,j} yen. (b_{i,j} \lt a_{i,j})
Find the following value for all pairs of cities (i, j) such that i \lt j:
- the minimum amount of money required to travel from city i to city j, using the voucher at most once in total.
Constraints
- 2 \leq N \leq 300
- 1 \leq b_{i,j} \lt a_{i,j} \leq 10^4 (i \lt j)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
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}
Output
Print the answer in the following format. Here, c_{i,j} denotes the minimum amount of money required to travel from city i to city j, using the voucher at most once.
c_{1,2} c_{1,3} \dots c_{1,N}
c_{2,3} \dots c_{2,N}
\vdots
c_{N-1,N}
Sample Input 1
4 4 8 5 6 8 3 1 6 1 5 2 1
Sample Output 1
1 4 1 5 2 1
For example, you can travel from city 1 to city 3 using the voucher at most once for a total cost of 4 yen, which is the minimum, as follows:
- Travel from city 1 to city 4 for a cost of 1 yen, using the voucher.
- Travel from city 4 to city 3 for a cost of 3 yen, without using the voucher.
Sample Input 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
Sample Output 2
43 3 1 42 10 7 12 11 3 37 6 46 94 4 85