自动搬运

查看原文

来自洛谷，原作者为

	Loser_Syx 不可逆の方が美しいから

搬运于2025-08-24 22:54:11，当前版本为作者最后更新于2024-01-07 13:14:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

转化一下题意。
你考虑边 $(i,j)$ 是否满足要求的本质，实际是求是否存在 $i\rightarrow j$ 的路径可以替换掉 $(i,j)$ 这个边。

然后就好做多了，Floyd 跑完每个点对的最短路后，枚举边 $(i,j)$ 再枚举一个断点 $k\ (k \neq i,j)$，看一下 $i\rightarrow k$ 的最短路加 $k\rightarrow j$ 的最短路是否小于等于 $a_{i,j}$，是就是不符合。

void solve() {
	int n = read();
	for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) a[i][j] = f[i][j] = read();
	for (int k=1;k<=n;++k) for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) f[i][j]=min(f[i][j], f[i][k]+f[k][j]);
	for (int i=1;i<=n;++i,putchar(10)) for (int j=1;j<=n;++j) {
		int ans=1;
		for (int k=1;k<=n;++k) if (i!=k&&j!=k&&f[i][k]+f[j][k]<=f[i][j]) ans=0;
		putchar(ans&&i!=j?'1':'0');
	}
}