KM行不行？

我怕我交上去会T，求大佬证明一下时间复杂度（

大概思路：

用 Floyd 求出最短路，然后每头牛向所有可以去的牛棚连边（一个牛棚会有很多个位置，我每个都连一遍）

最后跑了KM，求了最大的时间（

$1000$ 的数据我个人感觉还是有点大的，更何况实际上最多会有 $n\times 1000$ 个牛棚

求大佬解答