/ 
実行時間制限: 6 sec / メモリ制限: 1024 MiB
配点 : 475 点
問題文
N 頂点の重み付き無向木であって、以下の条件を満たすものが存在するか判定して下さい。
- 1 \le i \lt j \le N を満たす任意の 2 整数 i,j について頂点 i と頂点 j の距離が A_{i,j} である。
ただし、頂点 i と頂点 j の距離とは、この 2 頂点を結ぶ唯一の単純パスに含まれる辺の重みの総和のことです。
制約
- 2 \le N \le 3000
- 1 \le A_{i,j} \le 9999
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N
A_{1, 2} A_{1, 3} \ldots A_{1, N}
A_{2, 3} \ldots A_{2, N}
\vdots
A_{N-1,N}
出力
条件を満たす木が存在するなら Yes を、存在しないなら No を出力せよ。
入力例 1
4 2 5 4 3 2 5
出力例 1
Yes
例えば以下の辺をもつ木が条件を満たします。
- 辺 (1, 2) の重みが 2
- 辺 (2, 3) の重みが 3
- 辺 (2, 4) の重みが 2
よって Yes と出力してください。
入力例 2
4 2 5 4 3 2 6
出力例 2
No
条件を満たす木は存在しません。よって No と出力してください。
入力例 3
10 1039 1802 3781 231 5828 1944 392 262 1481 763 2742 1270 4789 905 1431 1301 442 1979 2033 5552 142 2194 2064 1205 4012 7531 2121 4173 4043 3184 6059 2175 161 493 1712 5694 6220 6090 5231 2336 2206 1347 654 1873 1743
出力例 3
Yes
Score : 475 points
Problem Statement
Determine whether there exists a weighted undirected tree with N vertices satisfying the following condition.
- For any two integers i and j with 1 \le i \lt j \le N, the distance between vertices i and j is A_{i,j}.
Here, the distance between vertices i and j is defined as the sum of the weights of the edges on the unique simple path connecting these two vertices.
Constraints
- 2 \le N \le 3000
- 1 \le A_{i,j} \le 9999
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
A_{1, 2} A_{1, 3} \ldots A_{1, N}
A_{2, 3} \ldots A_{2, N}
\vdots
A_{N-1,N}
Output
If a tree satisfying the condition exists, output Yes; otherwise, output No.
Sample Input 1
4 2 5 4 3 2 5
Sample Output 1
Yes
For example, the tree with the following edges satisfies the condition.
- Edge (1, 2) has weight 2.
- Edge (2, 3) has weight 3.
- Edge (2, 4) has weight 2.
Thus, output Yes.
Sample Input 2
4 2 5 4 3 2 6
Sample Output 2
No
No tree satisfying the condition exists. Thus, output No.
Sample Input 3
10 1039 1802 3781 231 5828 1944 392 262 1481 763 2742 1270 4789 905 1431 1301 442 1979 2033 5552 142 2194 2064 1205 4012 7531 2121 4173 4043 3184 6059 2175 161 493 1712 5694 6220 6090 5231 2336 2206 1347 654 1873 1743
Sample Output 3
Yes