Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:1024 MB

#2703. 最短最长最短路

Statistics

题目描述

给你一个竞赛图,令 $\mathrm{dist}(u,v)$ 表示从 $u$ 走到 $v$ 的最短路,如果无法从 $u$ 走到 $v$ 则为 $10^9$。 求 $\min_{1\le u \le n} \max_{1\le v \le n} \mathrm{dist}(u, v)$。

输入格式

第一行是输入一个 $T$, 接下来 $T$ 组数据。 每组数据第一行一个 $n$,接下来 $n$ 行长度为 $n$ 的 01 串 $a_{i,j}$,表示是否有 $i$ 到 $j$ 的有向边。

保证 $a_{i,i} = 0, \forall i\not=j, a_{i,j}+a_{j,i} = 1$。

输出格式

输出 $T$ 行,每行一个答案。

样例输入 1

2
4
0101
0000
1101
0100
5
01100
00010
01000
10101
11100

样例输出 1

1
2

数据范围

保证 $1 \le n \le 10000, a_{i, j} \in \{0, 1\}$。

数据点编号 $\sum n \le$
1, 2 20
3, 4 400
5, 6 1500
7, 8 5000
9, 10 10000

时间限制:1s

空间限制:1GB