創作內容

2 GP

最近在程設版看到一個問題

作者:♙♲⚙\~O_O~/⚙♲♙│2020-08-11 05:12:04│巴幣:4│人氣:148
問題如圖


我們來看看留言裡面有什麼答案


|V| = 500 * 500 = 25萬個點,這樣真的可以用Floyd–Warshall


這個問題的連通狀態是一直在改變的,與現實應用連結,可以想到封包怎麼送的問題


所以下面留言的Bellman–FordDijkstra都有機會

引用網址:https://home.gamer.com.tw/TrackBack.php?sn=4878744
All rights reserved. 版權所有,保留一切權利

相關創作

同標籤作品搜尋:=_=

留言共 2 篇留言

樂小呈
500 * 500 的網格用Dijkstra效能會爆吧[e21]

08-11 08:08

♙♲⚙\~O_O~/⚙♲♙
可能會 可能不會

25萬個點*每個點4條岔路=100萬
log2(25萬) ≒ 18
1800萬*某個我也不知道多少的係數

在C/C++
int s=0; for(int x=100000000;x--;) s=(s+x)&0x3FFFFFFF;
1億才會感覺到卡(大約0.2秒)

在javascript
s=0; for(let x=10000000;x--;) s+=x;
1千萬就會卡(大約0.5秒)08-11 10:52
♙♲⚙\~O_O~/⚙♲♙
我更正 一定爆 多做幾件事情就超過了 QQ08-11 11:04
樂小呈
但好像比較好的做法就是Dijkstra了[e21]

08-11 08:15

♙♲⚙\~O_O~/⚙♲♙
我的話應該是 用bfs以目標位置當起點硬上吧(25萬個點*每個點4條岔路=100萬,應該可以吧(?))
然後發現要加什麼東西都很難加 因為效能需求直接吃滿0.1秒 接著就想怎麼用A*剪枝
最後覺得整個寫太醜 直接把尋路變成智障型(greedy) 走不過去就放棄這樣08-11 10:26
♙♲⚙\~O_O~/⚙♲♙
啊 不行 他的邊權重不一樣 那要把queue改成priority queue
恩...Dijkstra \OvO/08-11 10:33
我要留言提醒:您尚未登入,請先登入再留言

2喜歡★agold404 可決定是否刪除您的留言,請勿發表違反站規文字。

前一篇:(已修好)沒有手機認證或... 後一篇:竟然100GP了...

追蹤私訊切換新版閱覽

作品資料夾

overozone《小剪男孩》
燈里是和你一起長大的夥伴,是很重要的家人吧!──凪玲長篇BL同人今日更新第22章,歡迎來看看~看更多我要大聲說昨天23:46


face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】