Informatika gyűjtemény

Egy szinttel feljebb Futár

2004050607080910

NézetNyomtat

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.

Feladat

Készíts 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\le N \le 100$: a városok száma
  • $1\le M \le 5000$: a járművek száma
  • $1\le H \le 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\le T \le 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

futar.befutar.ki
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