解法1: ダブリング

問題文を素直に読み取り，以下のような$D$を考えます．

$D_{l,u,v}$: ちょうど距離$l$走って，地点$u$から$v$に到着することができるか

すると，$D$について，以下の漸化式（DP）が成り立つことがわかります．（$\bigvee$は$\sum$の$+$演算が$\mathrm{OR}$演算になったものです．）

$D_{l+1,u,v} = \displaystyle \bigvee_{1 \leq w \leq N} D_{l,u,w} \ \mathrm{AND} \ A_{w,v}$

$D$の定義から，$D_0$は単位行列なので，これで$D_1$から順に$D_K$を求められそうです．
上の式通りに実装した時の，$D_n$から$D_{n+1}$を求める計算量を求めてみましょう．

全$2$点間について，

$\displaystyle \bigvee_{1 \leq w \leq N} D_{l,u,w} \ \mathrm{AND} \ A_{w,v}$

を求める計算量は$\mathrm{O}(N^3)$です．よって，$D_{K}$を求める計算量は$\mathrm{O}(N^3K)$となります．
しかし，この問題では$K$の制約が非常に大きく，この計算量では間に合いません．

ここで，任意の$x$について，以下の式が成り立つことに注目します．

$D_{2x,u,v} = \displaystyle \bigvee_{1 \leq w \leq N} D_{x,u,w} \ \mathrm{AND} \ D_{x,w,v} \qquad \dots \qquad (1)$

この式から，$D_{2^x}$を$\mathrm{O}(N^3X)$で求めることができることがわかります．また，$D_K$は，$D_{2^x}$を$\mathrm{O}(\log K)$個足し合わせることで求めることができるため，計算量は$\mathrm{O}(N^3\log K)$となります．

このテクニックを，ダブリングといいます．

しかし，この問題の制約では，$\mathrm{O}(N^3\log K) \geq 2 \times 10^9$であり，まだ高速化が必要です．

ここで，$(1)$式を求めるのにかかる計算量をもう一度考えてみましょう．ある$2$点間についてこれを求める計算量は$\mathrm{O}(N)$に見えますが，実際はもっと速く計算することができます．

$1 \leq N \leq 50$であることを思い出してください．最近の一般的なCPUでは，$64$個のbitの論理積は$1$命令で計算することができます．これを利用し，$N$個のbit論理積を$1$命令，つまり$\mathrm{O}(1)$でまとめて計算することができます．また，この$N$個のbitを論理和（$\mathrm{OR}$）した結果は，単にその論理積の結果が$0$か否かを確認すれば良いです．

以上の工夫により，$(1)$式は$\mathrm{O}(1)$で計算することができるため，上記解法の計算量を$\mathrm{O}(N^2\log K)$に落とすことが可能です．
$\mathrm{O}(N^2\log K) \simeq 5 \times 10^6$であるため，この解法は，この問題の実行時間制限に対して十分高速です．

解法2: 行列累乗

$D_{l,u,v} = \displaystyle \bigvee_{1 \leq w \leq N} D_{l-1,u,w} \ \mathrm{AND} \ A_{w,v}$

をよく見ると，行列の積の演算によく似ています．（$\bigvee$が$\sum$だったら行列の積ですね．）

実際，$(\{0,1\},\mathrm{OR})$は可換モノイド，$(\{0,1\},\times)$もモノイド，さらに$(\{0,1\},\times)$は$(\{0,1\},\mathrm{OR})$の上に分配的であることから，$(\{0,1\},\mathrm{OR},\times)$は半環であるため，$(\{0,1\},\mathrm{OR},\times)$を$(\mathbb{R},+,\times)$と思って行列累乗することで$\mathrm{O}(N^3\log K)$で$D_{K} = A^N$を求めることができます．

行列の積，和の実装で，上と同じくbit演算による工夫を行うことで$\mathrm{O}(N^2\log K)$で実装可能です．

※あえて解法1と解法2が別の回答かのように書きましたが，同じことをしています．