[理工] 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大瞬間懂怎麼解這題了

繼續閱讀