Ze struktur danych dostaliśmy wyobraźcie sobie do napisania program! Kto by pomyślał?
Oto treść:
Motel Dost˛epna pami˛e´ c: 64MB. Profesor Makary wybiera si˛e na zimowy urlop na narty. Poniewa˙ z droga z domu profesora do górskiego kurortu jest daleka, profesor liczy si˛e z konieczno´ sci ˛a podzielenia jej na dwa dzienne etapy, z noclegiem w przydro˙ znym motelu. Podró˙ ze go m˛ecz ˛a, wi˛ec tras˛e i miejsce na nocleg chce wybra´ c tak, ˙ zeby oba fragmenty drogi nie były zbyt długie. Dokładniej, chciałby, aby dłu˙ zszy z dwóch dziennych etapów był mo˙ zliwie najkrótszy. Pomó˙ z profesorowi zaplanowa´ c tras˛e dojazdu, pisz ˛ac program, który obliczy najmniejsz ˛a mo˙ zliw ˛a długo´ s´ c dłu˙ zszego etapu. UWAGA: Mo˙ ze si˛e zdarzy´ c, ˙ ze w optymalnym rozwi ˛azaniu który´ s z etapów ma długo´ s´ c 0 (czyli w rzeczywisto´ sci cała trasa zostanie przebyta w jednym etapie). Wej´ scie W pierwszym wierszu znajduj ˛a si˛e dwie liczby całkowite n i m (2 ? n ? 50000, 1 ? m ? 1000000). Pierwsza z nich oznacza liczb˛e punktów stanowi ˛acych potencjalne miejsca postoju, ponumerowanych od 0 do n?1 (punkt numer 0 to dom profesora, punkt n?1 to kurort, a pozostałe to motele). Druga to liczba odcinków dróg ł ˛acz ˛acych punkty. Ka˙ zdy z kolejnych m wierszy zawiera trzy liczby całkowite a, b, c, gdzie 0?a,b<n, a 6=b, 0?c?10000. Liczby a i b oznaczaj ˛a punkty na drogach, za´ s c to długo´ s´ c odcinka drogi prowadz ˛acego bezpo´ srednio od a do b. (UWAGA: długo´ sci odcinków dróg od a do b i od b do a nie musz ˛a by´ c równe; w szczególno´ sci który´ s z nich mo˙ ze wcale nie istnie´ c). Liczby w ka˙ zdym wierszu s ˛a pooddzielane pojedynczymi spacjami. Wyj´ scie W jedynym wierszu standardowego wyj´ scia nale˙ zy wypisa´ c najmniejsz ˛a mo˙ zliw ˛a długo´ s´ c dłu˙ zszego z dwóch etapów drogi z domu profesora do kurortu. Przykład Dla danych wej´ sciowych: 4 5 0 1 1 0 2 4 1 2 2 1 3 4 2 3 3 poprawnym wynikiem jest: 3 Wyja´ snienie do przykładu. Optymalna trasa to: 0?1?2 (I etap); 2?3 (II etap)
A oto rozwiązanie:
Jakoś działa, z większy naciskiem na JAKOŚ niż na DZIAŁA
Zadanie