Programozás‎ > ‎Feladatok‎ > ‎

Futár

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