Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?
I want the old design back!!! :-)

Problem S. 116. (April 2017)

S. 116. Subscribers can reach the text of the problem after signing in. The text will be public from April 28, 2017.]

(10 pont)

Deadline expired on May 10, 2017.


Sorry, the solution is available only in Hungarian. Google translation

Futtassunk le egy-egy Dijkstra algoritmust \(\displaystyle A\) és \(\displaystyle B\) kezdőponttal. legyen \(\displaystyle d_A[p]\) a \(\displaystyle p\) pont távolsága \(\displaystyle A\)-tól, illetve \(\displaystyle d_B[p]\) hasonlóan a távolság \(\displaystyle B\)-től.

Ezután minden \(\displaystyle p-q\) autópályára, ha oda építjük az új vonalat, akkor az A-B utat háromféleképpen tehetjük meg:

1) Az új vonal használata nélkül, a távolság \(\displaystyle d_A[B]\).
2) \(\displaystyle A\)-ból \(\displaystyle p\)-be autópályákon, majd az új vonalon \(\displaystyle q\)-ba, majd onnan \(\displaystyle B\)-be autópályákon, ekkor a távolság \(\displaystyle d_A[p]+d_B[q]\).
3) \(\displaystyle A\)-ból \(\displaystyle q\)-ba autópályákon, majd az új vonalon \(\displaystyle p\)-be, majd onnan \(\displaystyle B\)-be autópályákon, ekkor a távolság \(\displaystyle d_A[q]+d_B[p]\).

Az összes élre megnézve mindhárom lehetőséget, könnyen kiválaszthatjuk az optimálisat, megjegyezve a (egy) élet, ami optimalizálja a távolságot. A kódolás során ügyeljünk arra, hogy ha a távolság nem rövidíthető (1. eset az optimális), akkor is helyes eredményt adjon a program.

A csatolt program minden optimális élet kilistáz a kitűzött feladattal ellentétben.

Minta megoldás (c++)

Alternatív megoldás, hogy minden várost két pontként tárolunk a gráfban: az elsőben akkor vagyunk, ha még nem használtuk az új eszközt, a másodikban pedig akkor, ha már igen. Ha ezt a modellt választjuk, akkor a feladat csak a Dijkstra algoritmus triviális alkalmazása.


Statistics:

9 students sent a solution.
10 points:Busa 423 Máté, Kiss Gergely, Noszály Áron.
9 points:Vári-Kakas Andor.
8 points:4 students.
5 points:1 student.

Problems in Information Technology of KöMaL, April 2017