Floyd版动态规划

具体代码参考P1027 题解。只需要把Floyd的转移方程换为
\[ f[i, j, k] = f[i, j, k-1] \lor (f[i, k, k-1] \land f[k, j, k-1]) \]
其中\(\lor\)表示或，\(\land\)表示与。

代码为：

for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++) // i, j, k全部是从1~n
        for(int j=1;j<=n;j++)
            dis[i][j]=f[i][j] | (f[i][k] & f[k][j]);