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 |