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
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