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.  

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

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

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

Bemenet	Kimenet
8 15 4 5 0.35 5 4 0.35 4 7 0.37 5 7 0.28 7 5 0.28 5 1 0.32 0 4 0.38 0 2 0.26 7 3 0.39 1 3 0.29 2 7 0.34 6 2 0.40 3 6 0.52 6 0 0.58 6 4 0.93	0.60 0 2 7

A feladat forrása: közismert probléma

Algoritmusok: Dijkstra

megoldás