作者leegaga61029 (粒粒)
看板Grad-ProbAsk
标题[理工] 108交大资演 9
时间Tue Jan 28 23:39:18 2020
https://i.imgur.com/P8JGuQP.jpg
请问一下有人会这题吗QQ
追好久还是写错
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 101.12.133.75 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1580225960.A.3DA.html
1F：推 mistel: 用临接矩阵做Dijkstra's01/28 23:54
2F：→ mathtsai: 题目要问什麽01/29 00:15
※ 编辑: leegaga61029 (101.12.133.75 台湾), 01/29/2020 01:14:46
3F：推 Justapig: 这一题trace的时候其实就是先从priority queue找最小， 01/29 09:55
4F：→ Justapig: 然後再判断哪些需要decrease key，不过如果没有想到这个 01/29 09:55
5F：→ Justapig: 直接追踪也可以 01/29 09:55
6F：→ Justapig: 题目我记得是问u_max最後的值 01/29 09:56
8F：→ s42420808: 刚刚做的供参字丑抱歉 01/29 15:39
9F：→ mathtsai: 这题就是Dijkstra啊 只是他没用priority queue来存 01/29 22:09
10F：→ mathtsai: 目前距离最小的点而已 01/29 22:10
11F：→ mathtsai: 他在找当前最小点的时候 花了O(V)来找而已 01/29 22:12