P10048 [CCPC 2023 Beijing Municipal Contest] Graph

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)$.

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 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$.

Translated by ChatGPT 5