You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有一张 $n$ 个点的有向图，对于任意 $1 \leq i, j \leq n$ 但是 $i \neq j$，若 $a_{i, j} \neq -1$ 那么有一条从 $i$ 到 $j$ 的边权为 $a_{i, j}$ 的有向边。

设 $\operatorname{dis}(i, j)$ 表示从 $i$ 到 $j$ 的最短路径的长度，特别地，若最短路径不存在，则 $\operatorname{dis}(i, j) = -1$。

对于所有 $1 \leq x \leq n$，你需要求解如下问题：假如删掉结点 $x$，那么剩下的 $n - 1$ 个点中，对于所有有序点对 $(i, j)$，$\operatorname{dis}(i, j)$ 的和。

为了方便，你只需要输出这 $n$ 个答案的和。

输入格式

第一行一个数 $n$。

接下来 $n$ 行，每行 $n$ 个数，第 $i + 1$ 行的第 $j$ 个数表示 $a_{i, j}$。

输出格式

一行一个数表示答案。

3
0 1 -1
100 0 2
-1 -1 0

100

数据范围

对于所有数据，保证 $3 \leq n \leq 500$，$-1 \leq a_{i, j} \leq 10^4$。

本题共 $10$ 个测试点，每个测试点的 $n$ 依次满足 $\leq 3, 10, 10, 80, 150, 200, 300, 400, 450, 500$。