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.
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