創作內容

2 GP

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

作者:☒404找不到│2020-08-11 05:12:04│贊助:4│人氣:61
問題如圖


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


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


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


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

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

相關創作

同標籤作品搜尋:=_=

留言共 2 篇留言

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

08-11 08:08

☒404找不到
可能會 可能不會

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
☒404找不到
我更正 一定爆 多做幾件事情就超過了 QQ08-11 11:04
is樂小呈
但好像比較好的做法就是Dijkstra了[e21]

08-11 08:15

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

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

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

追蹤私訊

作品資料夾

emeke6608貓狗鳥糞 貓狗蛔蟲
勤洗手重衛生動物糞便病毒寄生蟲勿入口 請搜尋 宿主を支配する微生物 新型隱球菌之感染與流行病學看更多我要大聲說9小時前


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

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