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.be | futar.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
