1 条题解
-
1XzyStudio (admin) LV 8 MOD 机房蒟蒻 tayz @ 2023-10-21 11:02:04
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]);
- 1