Susitikimas (2014)
Taškai: 9
Mieste, kuriame gyvena Agnė, Rytis ir Šarlotė, yra patogus metro tinklas. Pateikta tinklo schema, kurioje pavaizduotos metro stotys ir jas jungiantys keliai. Skaičius ties linija rodo, kiek bebų (vietinė bebrų valiuta) kainuoja nuvažiuoti tarp dviejų gretimų stotelių.
Agnė gyvena šalia Aguonų stotelės, Rytis – šalia Rytinės stotelės, Šarlotė – šalia Šermukšnių stotelės. Vaikai nori susitikti kurioje nors iš stotelių. Nei vienas iš jų negali išleisti daugiau nei 15 bebų, tačiau ir pėstute eiti nenori.
Kuriose stotelėse jie galėtų susitikti? Pažymėkite visas galimas susitikimo vietas.
Specifinis požiūris į ryšius tarp to paties rinkinio elementų yra vaizduojamas grafuose (rinkinys viršūnių ir briaunų, jungiančių viršūnių poras). Kai kuriuose grafuose briaunos gali turėti kryptį arba svorį. Šioje užduotyje grafo briaunos turi svorius, kurie nurodo kelionės kainą.
Yra sukurti efektyvūs algoritmai, padedantys rasti reikiamą kelią tarp grafo viršūnių. Akivaizdu, kad trumpiausio kelio algoritmai yra naudingi planuojant maršrutus. Pavyzdžiui, jei norite nuvykti nuo vienos stoties iki kitos kaip galima greičiau, tai pervežimo įmonės svetainėje bus pateiktas maršrutas, kuris apskaičiuotas pasinaudojus trumpiausio kelio algoritmu.
Algoritmas, kuris buvo naudojamas šiame uždavinyje norint rasti trumpiausią kelią, yra vadinamas E. Dijkstra algoritmu.
Teisingas atsakymas – Parko arba Aguonų stotelėse. Abu atsakymai yra teisingi.
Stotelės, į kurias važiuojant tiek iš Tvenkinių stotelės, tiek iš Rytinės bei iš Centrinės stotelių išleisime mažiau ar lygiai 15 bebų, ir bus mūsų uždavinio sprendiniai. Ieškant sprendimo reikia iš kiekvienos pradinės stotelės ieškoti pigiausio kelio iki kitos stotelės.
Pradėkime nuo Tvenkinių stotelės. Pradžioje mūsų išleista pinigų suma yra 0 bebų (Tvenkinių, 0). Toliau žiūrime į kokias stoteles galime nuvažiuoti iš Tvenkinių stotelės ir jų kainas: (Tvenkinių–Šiaurinė, 5), (Tvenkinių–Kampinė, 10) ir (Tvenkinių-Prekybos centro, 9). Taigi, pigiausiai iš Tvenkinių stotelės yra patekti į Šiaurinę stotelę: kainuoja 5 bebus, todėl toliau važiuojam iš Šiaurinės stotelės į Centrinę ir Kelmų stoteles ir skaičiuojam: (Tvenkinių–Centrinė, 8) ir (Tvenkinių-Kelmų, 7).
Dabar turime kelionių kainas į 5 stoteles: (Tvenkinių–Šiaurinė, 5), (Tvenkinių–Centrinė, 8), (Tvenkinių-Kelmų, 7), (Tvenkinių–Kampinė, 10) ir (Tvenkinių-Prekybos centro, 9). Toliau vėl iš kiekvienos galinės stotelės keliaujame į gretimas stoteles tol, kol kelionės kaina neviršija 15 bebų. Jeigu kaina viršijama – ši stotelė į sąrašą nebeįtraukiama.
Taip randame visas stoteles, į kurias galima vykti iš Tvenkinių stotelės už ne daugiau kaip 15 bebų.
Tuos pačius veiksmus pakartojame su Rytine ir Šermukšnių stotele ir randame dar du galinių stotelių sąrašus.
Palyginę visus tris galutinių stotelių sąrašus išrenkame visuose trijuose sąrašuose pasikartojančias stoteles.