Egy országban N város van. Az egyik városban futárok várakoznak.
Ismerjük azt is, hogy az egyes városokból mennyi idő alatt lehet elérni
valamilyen járművel adott másik városokat.
(Feltételezzük, hogy a futárok városából / "telephelyéről" az összes többi település elérhető megfelelő járművekkel.)
Feladat
Írjunk programot, ami megadja, hogy minimum mennyi idő alatt jutnak el a futárok az összes városba.
Bemenet
A bemenet első sora három számot tartalmaz:
- 1 <= N <= 100: a városok száma
- 1 <= M <= 5000: a járművek száma
- 1 <= H <= N: a futárok kezdő helye
Ezután M sorban a járművek leírása következik: az indulás és az érkezés
városának sorszáma, majd az út megtételéhez szükséges idő ( 1 <= T <= 1000).
Kimenet
A kimenet állományba egyetlen sort kell írni, a minimális időt, ami alatt a futárok az összes városba elérnek.
Példa
Bemenet |
Kimenet |
6 12 1 1 6 20
1 5 10
5 6 5
6 2 10
1 2 15
2 3 10
3 4 10
3 5 10
1 6 25
3 5 5
6 1 20
6 5 5
|
35
|
Magyarázat
1->5: 10 időegység 1->5->6: 15 időegység 1->2: 15 időegység 1->2->3: 25 időegység 1->2->3->4: 35 időegység
Tesztadatok
Címkék
A feladat forrása: NTOITV, 2010, 11-13. évfolyam, 2. forduló, 3. feladat
Algoritmusok: egy pontból kiinduló legrövidebb utak, Dijkstra-algoritmus
|