Programozás‎ > ‎Feladatok‎ > ‎

Szállítás

Az ország N városa között különböző teherbírású utak vannak. Két város között árut szeretnénk szállítani a lehető legnagyobb kapacitású teherautóval olyan útvonalon, ahol az autó tehersúlya nem nagyobb, mint az egyes utak teherbírása. 

Feladat

Írjunk programot, ami adott A és B városra megadja, hogy maximum mekkora tehersúlyú teherautó közlekedhet közöttük és merre kell menni!

Bemenet

A bemenet első sorában a városok száma (1 <= N <= 100), a köztük levő utak száma (1 <= M <= 10000), a kezdő és a cél város sorszáma (1 <= A ≠ B <= N) van, egy-egy szóközzel elválasztva. A következő M sor mindegyikében egy-egy út leírása található: azon két város sorszáma (1 <= sorszám <= N), amelyek között a kétirányú út vezet, valamint az út teherbírása (1 <= teherbírás <= 1000).

Kimenet

A kimeneti állományba 2 sort kell írni. Az elsőbe a maximális tehersúly kerüljön, a másodikba pedig az oda vezető úton levő városok sorszáma, egy-egy szóközzel elválasztva, az útvonal sorrendjében (azaz az első sorszám biztosan A, az utolsó sorszám biztosan B legyen)! Több megoldás esetén bármelyik megadható.

Példa

Bemenet  Kimenet
5 6 3 4
2 1 100
1 4 100
3 1 200
3 5 300
2 3 900
4 5 400
300
3 5 4


Tesztadatok

Címkék

A feladat forrása: NTOITV 2012 3. forduló, 11-13. évfolyam
Algoritmusok: 

megoldás