[理工] 108 中央资演 zxc78123 PTT批踢踢实业坊

楼主: zxc78123 (帮QQ) 2020-01-30 13:23:04

https://i.imgur.com/LUt8aFO.jpg
想问一下这题
是要先求出各点最短路径再求解吗
但是有八个点做完感觉要花不少时间
还是有其他的方法？

作者: s29441910 (灵机一笔) 2020-01-30 13:44:00

用Floyd-warshall求All pairs of vertex初值先画cost matrix，过程可以得到progress path，最后可以知道shortest path

作者: shinle14 2020-01-30 13:50:00

S大你做完就要交卷了吧

作者: s29441910 (灵机一笔) 2020-01-30 13:58:00

差不多吧XD

楼主: zxc78123 (帮QQ) 2020-01-30 14:02:00

那个精美8*8xD 现在是想说各点做Dijkstra 但好像也是要做很久

作者: gcobs0834 (gcobs0834) 2020-01-30 14:29:00

因为他是partial order所以算progress数量从屁股加回来就好了有点像从leaf 画回来生成树的感觉

作者: ponwar87123 (干我屁事喔北七) 2020-01-30 15:16:00

想问第6题你选什么我选C

楼主: zxc78123 (帮QQ) 2020-01-30 16:48:00

第六题我选acg大不太能理解你说的QQ 求出最短路径progress就知道了？

作者: s29441910 (灵机一笔) 2020-01-30 22:53:00

作者: ponwar87123 (干我屁事喔北七) 2020-01-31 12:32:00

10 AE 11 DE 12 ADE我写这个a到h的最短路径是13

作者: awemuse (退一步想海阔天空) 2020-02-01 12:53:00

无向图把h当起点算一次最短路径就好

楼主: zxc78123 (帮QQ) 2020-02-01 15:28:00

谢a大瞬间懂怎么解这题了

继续阅读