UOJ Logo

NOI.AC

4S 512MB

#2061. 方阵

统计

方阵

【问题描述】

给定一个 $n*n$ 方阵 A。判断是否满足以下条件:

  1. A[i][i]=0

  2. A[i][j]=A[j][i]

  3. A[i][j]<=max(A[i][k],A[k][j])

【输入格式】

第一行一个整数 n。

接下来 n 行,每行 n 个数字,表示一个方阵。

【输出格式】

如果合法则输出 0。

否则第一行输出违反的条件编号。

接下来一行三个数字表示具体的编号 i,j,k。

如果有多个违反条件的,输出字典序最小的

即,优先输出不满足条件1的,之后优先输出i最小的...

【样例输入1】

3

0 1 2

1 0 2

2 2 0

【样例输出1】

0

【样例输入2】

2

0 1

2 3

【样例输出2】

1

2 0 0

【数据规模】

测试点编号 n= 测试点编号 n=
1 300 11 1700
2 500 12 1800
3 700 13 1900
4 900 14 2000
5 1100 15 2100
6 1200 16 2200
7 1300 17 2300
8 1400 18 2400
9 1500 19 2500
10 1600 20 2500

对于所有数据,满足 0<=Aij<=1e9

请选手注意常数问题。

【时空限制】

4s,512MB