題意
一開始我想用Floyd去水水，發現水不過,第7組0.8S，第8組數據1.56S。于是想著用spfa去搞。
發現spfa原來這個好寫,不過中間由于大錯一個下標導致了1h的悲劇。。。至于spfa的介紹就不必我來說了吧，網上一搜一大把。
用spfa搞出來的最后一組數據用時0.19S。還過得去，不過網上有人說用spfa還可以優化，就是根據已經算出來的最短路來優化還沒算出的最短路，具體實現我不是很懂，給個鏈接，有興趣的看看。(這個鏈接里還有幾種最短路的算法效率的比較)
還有就是可以用heap+dij,不過這個heap最好還是自己手寫，想偷懶用stl的東西有時是要以時間為代價的。有時用stl的優先隊列來搞的話會超時，但是自己手寫堆的話，可能會比較理想。標稱給的就是heap+dij.具體實現nocow上應該有，這里就不貼了。