[Logo] Mendo Judge Discussion Board - Forums
  [Search] Search   [Recent Topics] Recent Topics   [Hottest Topics] Hottest Topics   [Members]  Member Listing   [Groups] Back to home page 
Кружна патека (2018) - Zosto e BFS presporo?  XML
Forum Index » Задачи од национални натпревари
Author Message
VlatkoSh


[Avatar]

Joined: 10/08/2016 12:39:15
Messages: 48
Offline

Link: http://mendo.mk/Task.do?id=801
Moj kod:




Ne razbiram zosto prosto BFS e presporo za zadacava. BFS ima O(V + E) kompleksnost, vo zadacava najlos slucaj e O(N + N*(N-1)/2) = O(N^2), ama ova nema smisla, bidekji odgovorot (najkratok pat od S do T) ke se najde relativno brzo. Ili gresam?

This message was edited 2 times. Last update was at 25/08/2018 12:25:56

petarsor



Joined: 15/07/2018 11:58:27
Messages: 87
Offline

VlatkoSh wrote:Link: http://mendo.mk/Task.do?id=801
Moj kod (dobiva TLE, malku optimiziran): http://mendo.mk/User_SubmissionSourceCode.do?id=274277

Ne razbiram zosto prosto BFS e presporo za zadacava. BFS ima O(V + E) kompleksnost, vo zadacava najlos slucaj e O(N + N*(N-1)/2) = O(N^2), ama ova nema smisla, bidekji odgovorot (najkratok pat od S do T) ke se najde relativno brzo. Ili gresam?


Gresis. Ne mozhe da ti go vidime kodot bidejki ne mozhe da se gledaat kodovi od drugi lugje preku link (mozhesh da go iskopirash na forumov), ama problemot e shto nekoi polinja kje gi pominuvash po povekje pati (ne znaesh koi ti se vekje poseteni).
Ako ti e klasicno BFS, znachi deka imash vnatre nekoj for koj gi izminuva site edgevi, pa mozhesh vnatre vo forot da stavish eden brojac i da ispechatish kolku operacii ti ima reshenieto (ako simnesh nekoj pogolem test primer od MENDO). Kje vidish deka e pogolem broj od N. So mapa mozhesh i da izbroish po kolku pati doagjash do sekoe pole.
VlatkoSh


[Avatar]

Joined: 10/08/2016 12:39:15
Messages: 48
Offline

Ja resiv posle 4 meseci Treba BFS i da se najde nacin voopsto da ne se razgledaat polinjata sto znaeme deka sme gi dodale vekje.
 
Forum Index » Задачи од национални натпревари
Go to:   
Powered by JForum 2.1.8 © JForum Team