33425번 - Junctions 다국어

문제

The streets and junctions of the Martian City can be represented as a weighted bidirectional complete graph where the $n$ junctions are the vertices and the streets are the edges. The weight of an edge is the length of the corresponding street.

For each edge $(a, b),ドル determine whether there exists a pair of vertices $(x, y)$ such that all shortest paths from $x$ to $y$ pass through the edge $(a, b)$.

입력

The first line contains a positive integer $n$ (1ドル \le n \le 500$) representing the number of junctions in the city.

Each of the next $n$ lines contains $n$ space-separated integers. Together, they form an $n \times n$ matrix. The number $a_{i, j}$ (1ドル \leq a_{i, j} \leq 10^6$) in the $i$-th row and $j$-th column represents the length of the bidirectional street between junctions $i$ and $j$. Specifically, $a_{i, i} = 0$ and $a_{i, j} = a_{j, i}$.

출력

Output a binary matrix of size $n \times n$ without spaces. The entry in the $i$-th row and $j$-th column must be 1ドル$ if the edge $(i, j)$ satisfies the conditions described in the problem, and 0ドル$ otherwise.

In particular, output 0ドル$ when $i = j$.

제한

힌트