題目很複雜，要多想一下下
題目敘述：
給你一個有向圖上每個邊權重的截距與斜率
要你找一天使得從起點到終點再回起點的權重和最小
剛想的時候，會覺得很困難
但多想一下，就會發現得到的答案一定會是 ( 某些權重和 + 某些斜率和 * Day )
於是盲點就破解了
若斜率和 > 0，Day = 0
否則，Day = maximum day( -> D )
所以就做兩次Dijkstra，一次是Day 0，一次是Day D，取 min
http://codepad.org/qepmJf30
沒有留言:
張貼留言