USACO Section 3.2 Sweet Butter

題目：

N 隻牛(<= 500)分散在 P 個牧場(<= 800)，給 C 條道路(<= 1450)的距離，

現在要選定一個牧場來集合所有的牛，問所有牛行走距離的最小值。

解法：

可以發現，當選定好目標牧場 G 時，

其他牧場到達 G 的最小花費一定是最短路，

故此題必須使用到最短路的演算法，

如：Dijkstra、SPFA、Floyd-Warshall ‧‧‧等，

枚舉所有牧場後再使用最短路求解，再取其中的最小值即可。

由於此題的邊數非常少，存圖時建議使用鄰接串列，速度會差很多，

以下是三種寫法的比較：

Dijkstra 加上 heap 優化後時間複雜度為 O((V+E)lgE)，於是總複雜度為 O(VElgE)，

結果如下：

   Test 1: TEST OK [0.000 secs, 3228 KB]

   Test 2: TEST OK [0.000 secs, 3228 KB]

   Test 3: TEST OK [0.000 secs, 3228 KB]

   Test 4: TEST OK [0.011 secs, 3228 KB]

   Test 5: TEST OK [0.011 secs, 3228 KB]

   Test 6: TEST OK [0.043 secs, 3228 KB]

   Test 7: TEST OK [0.076 secs, 3228 KB]

   Test 8: TEST OK [0.140 secs, 3228 KB]

   Test 9: TEST OK [0.227 secs, 3228 KB]

   Test 10: TEST OK [0.216 secs, 3228 KB]

SPFA 的複雜度為 O(kE)，其中 k 為一常數，總複雜度為 O(kVE)，

結果如下：

   Test 1: TEST OK [0.000 secs, 3228 KB]

   Test 2: TEST OK [0.000 secs, 3228 KB]

   Test 3: TEST OK [0.000 secs, 3228 KB]

   Test 4: TEST OK [0.000 secs, 3228 KB]

   Test 5: TEST OK [0.011 secs, 3228 KB]

   Test 6: TEST OK [0.022 secs, 3228 KB]

   Test 7: TEST OK [0.065 secs, 3228 KB]

   Test 8: TEST OK [0.065 secs, 3228 KB]

   Test 9: TEST OK [0.108 secs, 3228 KB]

   Test 10: TEST OK [0.119 secs, 3228 KB]

由於當起點枚舉到 S 時，以 1 到 S-1 為起點的最短路徑都已算過，

故可以取離 S 最接近之 S' 來估出一個不錯的距離，

此優化結果如下：

   Test 1: TEST OK [0.000 secs, 5788 KB]

   Test 2: TEST OK [0.000 secs, 5788 KB]

   Test 3: TEST OK [0.000 secs, 5788 KB]

   Test 4: TEST OK [0.000 secs, 5788 KB]

   Test 5: TEST OK [0.011 secs, 5788 KB]

   Test 6: TEST OK [0.011 secs, 5788 KB]

   Test 7: TEST OK [0.043 secs, 5788 KB]

   Test 8: TEST OK [0.065 secs, 5788 KB]

   Test 9: TEST OK [0.065 secs, 5788 KB]

   Test 10: TEST OK [0.054 secs, 5788 KB]

速度快了一倍左右，SPFA 在稀疏圖的表現看起來很不錯，

關於詳細的比較可以參考 最短路算法效率，有完整的實測結果。