https://imgur.com/EauPyUy
如圖，爬很久的文好像都沒有看到，也找不到解答@@
想請問這題
(a)我想到的方式是以c(u)+r(u,v)做為成本做Dijkstra's algo.
不知道這樣對不對？
(b)就更不知道了，要如何證明這樣算就會是最佳解呢？
謝謝
a 差不多 b 證明費氏堆積有最好的時間表現 詳細我好懶XD
這是DAG的最短路徑搜尋吧可以在V+E的時間完成Direct Acyclic Graph先對圖做拓譜排序 再依照排序順序做relax拓譜排序用dfs 每當 finish就把點放到排序的前端Topology Sort : O(|V|+|E|)對每個點做relax O(|V|)
作者:
leoone (里歐一代)
2017-12-13 18:25:00不知為何當初寫這題我會用bellman-ford去解 ==
想問T大，雖知dag最快沒錯，但證明的部分你會怎麼下手？直接比較其他algo的複雜度？
證明直接說我不會XD 不過配分15一定要掰一下畢竟資料量就已經是O(V+E)了我想掰一下應該不會太低我覺得這種證明應該沒幾個人寫得出來別怕
這年的證明不能掰，會倒扣，看一下原本考卷就知道了雖然看題幹的風格很明顯知道是哪位大老出的，但跟往年的考古風格差異太大，我是覺得鑑別度不太高第一面簡單到有基本概念就會寫，第二面大家如果都不敢寫證明的話，分數就只有50,60,70三種，我是拿60而且一般演算法的課也不太教證明，遇到這種考卷就放開心一點，反正大家分數都差不多
我當時是寫DAG這份應該只扣最後一小題空著的分數至於DAG的algo當時我有背 順便加減分析一下分數就到手了
我想問個問題 這題這樣出有什麼用意嗎 我第一眼以為要考dp + greedy這種oops 我看懂了 那當我沒問QQ