815
[usaco]單源最短路徑：3.3.5 Sweet Butter
https://hi.baidu.com/leokan/blog/item/3f69222ebfdbea544ec226fb.html
原文我就不貼了，直接貼另一個博客，感興趣的可以看看這位大神的解法。
上邊這個博客的作者用的是SPFA解法。
其實這道題也就是讓求某幾個點到其他所有的點的最短路徑，我用的是Dijkstra 算法，
不過由於本題是一個非常稀疏圖，使用鄰接矩陣遍曆的時候會非常的耗時間。
如果按普通的算法，時間複雜度在O（N^3）。
我做了一些優化，給稀疏圖加上了一層索引，直接找那些相鄰的邊。相當於是同時使用了鄰接矩陣和臨界表。
看測試結果：
Test 1: TEST OK [0.000 secs, 9632 KB]
Test 2: TEST OK [0.000 secs, 9632 KB]
Test 3: TEST OK [0.000 secs, 9632 KB]
Test 4: TEST OK [0.000 secs, 9632 KB]
Test 5: TEST OK [0.000 secs, 9632 KB]
Test 6: TEST OK [0.027 secs, 9632 KB]
Test 7: TEST OK [0.135 secs, 9632 KB]
Test 8: TEST OK [0.405 secs, 9632 KB]
Test 9: TEST OK [0.945 secs, 9632 KB]
Test 10: TEST OK [0.891 secs, 9632 KB]
最複雜的兩組結果是9和10；看出來索引對於不同分布的圖性能上是有很大差別的。
看了useco的算法，是用最小化堆實現的Dijkstra算法。
我的Dijkstra算法是直接搜索最小值，因此效率是O（N）；
而最小化堆，檢索效率是O（1），插入刪除的效率是O（logn）。由於這個查找最小值的操作位於循環內部，所以效率會有明顯的提高。
最後更新：2017-04-02 06:51:53