路径之和

题目描述

对于一张有向图，定义$d(x,y,z)$为从$x$号点出发，不经过$y$号点，最终到达$z$号点的最短路径长度，如果不存在这样的路径，$d(x,y,z)$的值为$-1$。

现在给定有向图中每两个点之间的有向边长度，求对于所有满足$1 \leq x,y,z \leq n$（$x \neq y$，$y \neq z$）的有序数对$(x,y,z)$，求它们$d(x,y,z)$的和。也就是求对于每个$y$，求除了$y$之外，其余的所有点组成的有序点对$(x,z)$不经过$y$的最短路径长度之和（不存在即为$-1$）。

输入格式

第一行输入一个正整数$n$，表示点数。

接下来输入$n$行，每行输入$n$个整数，第$i$行第$j$个数$G_{i,j}$表示从$i$号点到$j$号点的有向边长度，如果这个数为$-1$，则表示不存在从$i$号点到$j$号点的有向路径。

输出格式

输出一个整数表示答案。

数据范围与提示

• 对于$10\%$的数据，$n \leq 10$；
• 对于$40\%$的数据，$n \leq 50$；
• 另有$10\%$的数据，除$G_{i,i}=0$以外的所有边，边权相等且不为$-1$；
• 对于$100\%$的数据，$3 \leq n \leq 320$，$-1 \leq G_{i,j} \leq 10^{4}$，$G_{i,i}=0$。

样例

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

100

见example_sum2.in

见example_sum2.out

见example_sum3.in

见example_sum3.out