Problem Description

Given an undirected complete graph with $n$ vertices and positive edge weights, 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 $(a,b)$.

Input Format

The first line contains a positive integer $n \ (1 \le n \le 500)$, representing the number of vertices in the graph.

The next $n$ lines each contain $n$ numbers, forming an $n \times n$ matrix. The number $a_{i,j} \ (1 \leq a_{i,j} \leq 10^6)$ in row $i$ and column $j$ represents the length of the edge between $(i,j)$. In particular, $a_{i,i} = 0$.

It is guaranteed that $a_{i,j} = a_{j,i}$.

Output Format

Output a $01$ matrix of size $n$. The value in row $i$ and column $j$ is $1$ if the edge $(i,j)$ satisfies the requirement stated in the problem, and $0$ otherwise.

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

4
0 3 2 100
3 0 8 100
2 8 0 10
100 100 10 0

0110
1000
1001
0010

Hint

Translated by ChatGPT 5