P1119 灾后重建（Floyd算法优化）本题是一道Floyd算法的应用。Floyd算法是基于动态规划方程的推导而来，利用每一个合理的中间点来实现对两点之间距离的更新，具体的状态表达方程为：其中还有一些细节需要注意，本题给出了每一个村庄重建的时间，而这就需要我们额外注意，如果我们每次进行Floyd算法求询问中的两点最短路径那么时间复杂度就为O（q * n^3）,显然已经超过了我们的所给时间，而事实