解法1: ダブリング

問題文を素直に読み取り,以下のようなDDを考えます.

Dl,u,vD_{l,u,v}: ちょうど距離ll走って,地点uuからvvに到着することができるか

すると,DDについて,以下の漸化式(DP)が成り立つことがわかります.(\bigvee\sum++演算がOR\mathrm{OR}演算になったものです.)

Dl+1,u,v=1wNDl,u,w AND Aw,vD_{l+1,u,v} = \displaystyle \bigvee_{1 \leq w \leq N} D_{l,u,w} \ \mathrm{AND} \ A_{w,v}

DDの定義から,D0D_0は単位行列なので,これでD1D_1から順にDKD_Kを求められそうです.
上の式通りに実装した時の,DnD_nからDn+1D_{n+1}を求める計算量を求めてみましょう.

22点間について,

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

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

ここで,任意のxxについて,以下の式が成り立つことに注目します.

D2x,u,v=1wNDx,u,w AND Dx,w,v(1)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)

この式から,D2xD_{2^x}O(N3X)\mathrm{O}(N^3X)で求めることができることがわかります.また,DKD_Kは,D2xD_{2^x}O(logK)\mathrm{O}(\log K)個足し合わせることで求めることができるため,計算量はO(N3logK)\mathrm{O}(N^3\log K)となります.

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

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

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

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

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

解法2: 行列累乗

Dl,u,v=1wNDl1,u,w AND Aw,vD_{l,u,v} = \displaystyle \bigvee_{1 \leq w \leq N} D_{l-1,u,w} \ \mathrm{AND} \ A_{w,v}

をよく見ると,行列の積の演算によく似ています.(\bigvee\sumだったら行列の積ですね.)

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

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

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