A - Copy and Paste Graph Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

N 行 N 列の行列 A=(a_{i,j}) が与えられます。ここで、a_{i,j} \in \{0,1\} が成り立ちます。

また、以下のような有向グラフがあります。

  • 頂点数は NK で、各頂点には 1,2,\ldots,NK と番号が付けられている。
  • 辺は A を縦 K 行横 K 列に並べて得られる NK 行 NK 列の行列 X=(x_{i,j}) によって表される(入出力例1にて A, K に対応する X が示されている)。具体的には、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

辺が 1 本も存在しません。

Score : 300 points

Problem Statement

You are given an N-by-N matrix A=(a_{i,j}), where a_{i,j} \in \{0,1\}.

We have the following directed graph.

  • The graph has NK vertices numbered 1,2,\ldots,NK.
  • The edges correspond to the NK-by-NK matrix X=(x_{i,j}) obtained by arranging K^2 copies of A in K rows and K columns (see Sample Input/Output 1 for an example). If x_{i,j}=1, there is a directed edge from vertex i to vertex j; if x_{i,j}=0, that edge does not exist.

Answer the following question for i=1,2,\ldots,Q.

  • Find the shortest length (number of edges) of a path from vertex s_i to vertex t_i. If there is no such path, print -1 instead.

Constraints

  • 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
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print Q lines. The x-th line should contain the answer to the question for i=x.

Sample Input 1

3 2
1 1 1
1 1 0
0 1 0
4
1 2
1 4
1 6
6 3

Sample Output 1

1
1
1
3

Below is the matrix X representing the edges.

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

Sample Input 2

4 1000000000
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1
1 4000000000

Sample Output 2

-1

There is no edge.