R - Ranč

Časový limit: 4s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Cowboy Bob má ranč v Novom Mexiku, na ktorom chová stádo kráv. Keď Bob dostane kontrakt na predaj kráv musí odviesť stádo cez prériu ku železničnej stanici, kde naloží na vlak všetky kravy, ktoré sú zdravé a majú dobrú hmotnosť. Bob po predaji nakúpi zásoby a vyberie sa naspať na ranč so zarobenými peniazmi, kúpeným tovarom a kravami, ktoré sa už do vlaku nezmestili alebo neboli vhodné. Bob chce ísť z ranča ku železničnej stanici najkratšou cestou, aby kravy počas cesty veľmi nestratili na hodnote. Aby cestou späť nešiel Bob s kravami cez spasené miesta a cesty, naspať od stanice na ranč chce Bob ísť takou najkratšou cestou, ktorá nemá žiadne spoločné miesto (a teda ani cestu) s cestou z ranča ku stanici okrem ranča a stanice. Napíšte Bobovi cestu z ranča ku železničnej stanici a späť.

Úloha

Vypíšte cestu z ranča ku železničnej stanici a späť na ranč.

Vstup

Vstupom je mapa ciest na prérii. Prvý riadok obsahuje počet miest na prérii N (počet vrcholov, kde 3 ≤ N ≤ 100), počet ciest spájajúcich miesta M (počet hrán, 3 ≤ M ≤ 4 950), miesto Bobovho ranča a miesto železničnej stanice. Pre jednoduchosť miesta sú očíslované od 0 po N-1. Nasledujúcich M riadkov obsahuje tri celé nezáporné čísla, prvé dve čísla vyjadrujú miesta na prérii a tretie číslo vyjadruje vzdialenosť daných miest, pričom predpokladáme, že všetkými cestami sa dá chodiť oboma smermi.

Výstup

Výstup obsahuje jeden riadok popisujúci cestu z ranča ku železničnej stanici a späť na ranč, medzerou oddelené miesta na prérii.

Príklad

Vstup

UPJŠ ŠVK 2019