分数: 300 点
问题陈述
你被给予 N-by-N 矩阵 A=(a_{i,j}),其中 a_{i,j} \in \{0,1\}.
我们有以下有向图。
- 该图有 NK 顶点编号 1,2,\ldots,NK.
- 边缘对应于 NK-by-NK 矩阵 X=(x_{i,j}) 通过排列获得 K^2 副本 A in K 行和 K 列(有关示例,请参阅示例输入/输出 1)。如果 x_{i,j}=1,从顶点有一条有向边 i 到顶点 j;如果 x_{i,j}=0,该边不存在。
回答以下问题 i=1,2,\ldots,Q.
- 查找从顶点开始的路径的最短长度(边数) s_i 到顶点 t_i。如果没有这样的路径,则打印
-1。
约束
- 1 \leq N \leq 100
- 1 \leq K \leq 10^9
- a_{i,j} \in \{0,1\}
- 1 \leq Q \leq 100
- 1 \leq s_i,t_i \leq NK
- s_i \neq t_i
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N K
a_{1,1} \ldots a_{1,N}
\vdots
a_{N,1} \ldots a_{N,N}
Q
s_1 t_1
\vdots
s_Q t_Q
输出
打印 Q 行。的 x- 第行应包含问题的答案 i=x.
示例输入 1
3 2 1 1 1 1 1 0 0 1 0 4 1 2 1 4 1 6 6 3
示例输出 1
1 1 1 3
下面是矩阵 X 代表边缘。
1 1 1 1 1 1 1 1 0 1 1 0 0 1 0 0 1 0 1 1 1 1 1 1 1 1 0 1 1 0 0 1 0 0 1 0
示例输入 2
4 1000000000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 4000000000
示例输出 2
-1
没有边缘。