AT_past17_l.割引券

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有 $N$ 个城市，编号为 $1$ 到 $N$ 。
任意两个不同的城市之间都有一条双向收费公路。你有一张代金券，可以在任意一条道路上使用该券以折扣价通过。
城市 $i$ 和城市 $j$ 之间（ $i < j$ ）的普通通行费为 $a_{i,j}$ 日元；使用代金券后的通行费为 $b_{i,j}$ 日元（ $b_{i,j} < a_{i,j}$ ）。

对于所有满足 $i < j$ 的城市对 $(i, j)$ ，求：

从城市 $i$ 到城市 $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
```

输入#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

说明/提示

样例解释 1

例如，你可以从城市 $1$ 出发，最多使用一次代金券，以总费用 $4$ 日元到达城市 $3$ ，具体如下：

从城市 $1$ 到城市 $4$ ，使用代金券，花费 $1$ 日元。
然后从城市 $4$ 到城市 $3$ ，不使用代金券，花费 $3$ 日元。

数据范围

$2 \leq N \leq 300$
$1 \leq b_{i,j} < a_{i,j} \leq 10^4$ ，其中 $i < j$
所有输入值均为整数。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页