Programozás‎ > ‎Feladatok‎ > ‎

Legrövidebb utak

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.

Bemenet

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.

Kimenet

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.

Példa

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


Tesztadatok

Kihívás: http://algs4.cs.princeton.edu/44sp/largeEWD.txt (1 millió csúcs, 15 millió él)

Címkék

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

megoldás