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