題目網址: http://poj.org/problem?id=2662
題意: 要從辦公室走回家會經過一片森林，給定森林的點(包含辦公室-點1、家-點2)，且要求若在點A上能有邊至點B，且從B回到家比從A回到家快，就可以考慮往B走，問從點1走到點2，有幾種走法。
解法: 先求出以點2為起點至每個點的最短路徑長度(SPFA)，後以DP計算方法數，dp[i]代表從點i出發能夠走到點2的方法數，而狀態轉移方程:
dp[i] = { 1, if i == 2
{ += dp[j], if i到j有邊 && d[i] > d[j]
再以DFS從點1出發走過整個圖，最後答案即為 dp[1]。
*d[i]代表以點2為起點到點i的最短路徑長度
TAG: SPFA, DP, DFS
注意: None
程式碼:
沒有留言:
張貼留言
任何意見都樂意傾聽