AT_agc036_d [AGC036D] Negative Cycle

[problemUrl]: https://atcoder.jp/contests/agc036/tasks/agc036_d $ 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\

N/A

N/A

### 制約 - $ 3\ \leq\ N\ \leq\ 500 $ - $ 1\ \leq\ A_{i,j}\ \leq\ 10^9 $ - 入力される値はすべて整数である。 ### Sample Explanation 1 すぬけさんが追加した辺 $ (0\ →\ 1) $ を削除すると、グラフに負閉路がないようになります。 この時必要なコストは $ 2 $ で、これが最小です。 ### Sample Explanation 2 すぬけさんが追加した辺 $ (1\ →\ 2) $ と $ (3\ →\ 0) $ を削除すると、グラフに負閉路がないようになります。 この時必要なコストは $ 1+1=2 $ で、これが最小です。