AT_agc036_d.[AGC036D] Negative Cycle

有一个包含 $N$ 个顶点的带权有向图，顶点编号为 $0$ 到 $N-1$。

最初，这个图中有 $N-1$ 条边。第 $i$ 条边（$0 \leq i \leq N-2$）是从顶点 $i$ 到顶点 $i+1$ 的一条权值为 $0$ 的有向边。

接下来，すぬけさん将对所有 $i, j$（$0 \leq i, j \leq N-1, i \neq j$）进行如下操作：新增一条从 $i$ 到 $j$ 的有向边。如果 $i < j$，则这条边的权值为 $-1$，否则权值为 $1$。

りんごくん如果发现图中存在负环（即环上所有边的权值和小于 $0$），会非常难过。因此，他打算从すぬけさん新加的边中删除若干条，使得最终的图中不包含负环。删除すぬけさん新加的边 $(i \to j)$ 需要花费 $A_{i,j}$ 的代价。注意，最初存在的 $N-1$ 条边不能被删除。

请你求出，为了让最终的图中不包含负环，所需删除边的总代价的最小值。

输入以如下格式从标准输入给出。

$N$ $A_{0,1}$ $A_{0,2}$ $A_{0,3}$ $\cdots$ $A_{0,N-1}$ $A_{1,0}$ $A_{1,2}$ $A_{1,3}$ $\cdots$ $A_{1,N-1}$ $A_{2,0}$ $A_{2,1}$ $A_{2,3}$ $\cdots$ $A_{2,N-1}$ $\vdots$ $A_{N-1,0}$ $A_{N-1,1}$ $A_{N-1,2}$ $\cdots$ $A_{N-1,N-2}$

输出一个整数，表示为达成目标所需删除边的总代价的最小值。

数据范围

• $3 \leq N \leq 500$
• $1 \leq A_{i,j} \leq 10^9$
• 所有输入均为整数。

样例解释 1

如果删除すぬけさん新加的边 $(0 \to 1)$，则图中将不再有负环。此时所需总代价为 $2$，且这是最小值。

样例解释 2

如果删除すぬけさん新加的边 $(1 \to 2)$ 和 $(3 \to 0)$，则图中将不再有负环。此时所需总代价为 $1+1=2$，且这是最小值。

由 ChatGPT 4.1 翻译