为何Floyd-Warshall算法在N=500时可在1秒内完成运行？

• “1秒可完成10⁸次运算”是针对含复杂逻辑操作的通用估算值，并非所有运算的统一上限。Floyd-Warshall的核心迭代仅包含简单的算术比较操作dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])，现代CPU单核心每秒可执行数十亿次这类轻量化操作，远高于10⁸的基准数值。
• 编译器优化可带来数倍性能提升：CSES的C/C++评测默认开启O2优化，会对三重循环做循环展开、指令重排、自动向量化等优化，大幅降低实际运行耗时。
• 缓存命中率极高：500×500的距离矩阵若存储为4字节整型，总大小仅为1MB，完全可以放入CPU的L1/L2缓存中，且算法的内存访问为连续顺序访问，几乎不会出现缓存失效的情况，内存访问延迟被极大掩盖。
• 1.25×10⁸次操作的量级本身远未到1秒的性能阈值：即使按保守的每秒5×10⁸次简单运算估算，1.25×10⁸次操作也仅需0.25秒即可完成，远低于1秒的时间限制。

内容的提问来源于stack exchange，提问作者Pioneer