close
先把為何需要反向圖寫下來,之後再填程式碼。
左邊的圖是原本的graph,右邊是inverse graph
這一題需要vertex 1 到所有點的距離總合 加上 所有點到 vertex 1 的距離總合
而在原本的graph 中 vertex n 到 vertex 1的距離 相等於 inverse graph中 vertex 1 到 vertex n的距離
因此,要求所有頂點到 vertex 1 的距離就是在 inverse graph 中從 vertex 1 對所有點找最短路徑
全站熱搜
留言列表