P10048

Loser_Syx · 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');
    }
}