I came across this problem in an online judge: We are given a distance matrix consisting of $N$ rows and columns. The $i$th line of $j$th row is the distance between node $i$ and $j$ (not necessarily neighbors). The task is to find out if there exists a tree satisfying the given distance matrix or not. The only constraint is $1 \le N \le 2000$ and the time limit is 1 second.
Some sample test cases for clarity:
Input: N = 3 0 2 7 2 0 9 7 9 0 Output: True Input: N = 3 0 1 1 1 0 1 1 1 0 Output: False
I couldn't find an answer that is feasible for implementing in a short period of time (this is kind of important for me as I participate in competitions sometimes). An idea came to my mind is that to take the distance matrix as it was an adjacency matrix and compute MST, and then run Dijkstra's SSSP from each vertex through this MST and generate a new distance matrix and finally compare if the initial distance matrix and the matrix we found are identical. I know that this solution is not efficient nor logical (and also I'm not sure if this would work correctly) and that's why I'm posting here for an answer. I can tell that the solution involves DSU (Disjoint Set Union) and DFS from the problem tags but it just didn't come to my mind.