题解

思路

复制后的矩阵中，一条边是否存在只取决于两个端点编号减一后模 $N$ 的余数，因此可以把所有顶点压缩成 $N$ 个余数点。

做法

查询 $(s,t)$ 对应余数 $(s-1)\bmod N,(t-1)\bmod N$，它们之间的最短非空路径长度与原图相同。

在余数图上做 Floyd。对角线不能预设为零：原题保证 $s\ne t$，但二者可能来自不同副本而映射到同一余数，此时需要真正的自环或有向环才能到达。

复杂度

只把矩阵中的边置为 1，其他距离置为无穷，再正常转移即可；复杂度为 $O(N^3+Q)$，空间为 $O(N^2)$。