T584346 「2025 YAC Round 5」小五的完全图

小五有一个 $n$ 个点的带权无向完全图。现在，小五想要知道：对于每一条边 $(u, v)$，是否存在一个点对 $(x, y)$ 使得 $x \rightarrow y$ 的所有最短路都经过 $(u, v)$。

第一行输入一个正整数 $n $ $（1 \le n \le 500）$ ，表示图的点数。 接下来 $n$ 行每行 $n$ 个数，构成一个大小为 $n\times n$ 的矩阵 $g$。第 $i$ 行第 $j$ 个数 $g_{i,j}$ $（1\leq g_{i,j}\leq 10^6）$ 表示 $i$ 和 $j$ 之间边的长度。特别地，$g_{i,i} = 0$。 保证 $g_{i,j}=g_{j,i}$。

输出一个大小为 $n$ 的 $01$ 矩阵，其中第 $i$ 行第 $j$ 列为 $1$ 表示边 $(i,j)$ 满足题目中提出的要求，$0$ 表示不满足。 特别的，当 $i=j$ 时输出 $0$。