Adott egy irányított gráf pozitív valós élsúlyokkal. Határozzuk meg két csúcsa között a legrövidebb utat.
FeladatÍrjunk programot, ami kiírja a legrövidebb út hosszát a legkisebb indexű csúcsból a legnagyobb indexűbe, és megadja, hogy mely csúcsokon keresztül vezet a legrövidebb út.
BemenetA bemenet első sora csúcsok, második sora az élek számát adja meg. Ezután az élek következnek, soronként egy: honnan, hova, milyen hosszú. Az élek súlya 0 és 1 közé eső valós szám. A csúcsokat 0-tól (N-1)-ig sorszámozzuk.
KimenetAz első sorba a 0.-ból az (N-1).-be vezető legrövidebb út hosszát kell írni, a másodikba pedig a legrövidebb út által érintett csúcsokat.
Példa
Tesztadatok
CímkékA feladat forrása: közismert probléma
Algoritmusok: Dijkstra
megoldás |
Programozás > Feladatok >