很棒的例題!
因為他說一個點只能走一次 (除了起點跟終點)
那乍看之下就是一個Max flow的結構了 (拆點型)
再加上它需要最少的距離
那就是一個Minimum Cost Max flow
這是我第一次寫最小成本流
首先你用一個Source出發 走到了 Sink
你使用的是SPFA去走負權邊有向圖 求出最短距離
再用Max flow的方法去做Augmenting Path即可
文章標籤
全站熱搜
- 7月 30 週四 200915:17
PKU - 3068 "Shortest" pair of paths