題目：http://poj.org/problem?id=3268
有向圖加權圖N個點(N<=1000)、M條邊(M<=100000)
權重都是正的
問對於一個給定的點X，
求點對(X,i)使得(X到i的最短路徑+i到X的最短路徑)最大
程式碼：http://codepad.org/Kaibk8NR
如何找出各個i點它們到X點分別的最短路徑？
這題如果作N次Dijkstra會超時
腦筋一轉發現只要另建一個反向圖、也是以X為起點
這麼答案就出來了
為了codebook上寫Dijkstra、前向星、Heap所作的題目
只要模組化做得好
不管是建反向邊或是多次DFS、BFS啥的都能把code寫得很漂亮呢
沒有留言:
張貼留言