ARC159解题报告

比赛传送门

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;
}