A. Copy and Paste Graph
题意： 给定一个 \(n\times n\) 的邻接矩阵，将其复制 \(k^2\) 遍（行和列各 \(k\) 个），得到一个 \(nk\) 个点的有向图。有 \(q\) 次询问，每次询问 \(s\to t\) 的最短路长度（或不可达）。\(n,q\le 100, k\le 10^9\)。
考察一个点 \(x\) 在新图上能到达哪些点，设其为 \(pn+q(1\le q\le n)\)，则容易发现其能到达 \(p'n+q'(q\to q')\)。所以，本质上此题的图对于不同的 \(p\) 是等价的，且可以直接到达不同的 \(p\)。于是可以对原来的 \(n\times n\) 的图跑 Floyd，答案即为 \(q_s\to q_t\) 的最短路。
By zhoukangyang
const int N = 107;
ll n, k;
int G[N][N];
int main() {
ios :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> k;
L(i, 1, n) {
L(j, 1, n) {
cin >> G[i][j];
if(G[i][j] == 0)
G[i][j] = 1e9;
}
}
L(k, 1, n)
L(i, 1, n)
L(j, 1, n)
G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
int q;
cin >> q;
while(q--) {
ll x, y;
cin >> x >> y;
x = (x - 1) % n + 1;
y = (y - 1) % n + 1;
if(G[x][y] > n)
cout << -1 << '\n';
else
cout << G[x][y] << "\n";
}
return 0;
}