In the event of technical difficulties with Szkopuł, please contact us via email at szkopul@fri.edu.pl.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (irc.pirc.pl
) in #szkopul
channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
W Bajtlandii sieć dróg między miastami jest taka, że między dwoma dowolnymi miastami istnieje dokładnie jedna droga (bezpośrednia lub pośrednia). Pewien kupiec przyjechał do Bajtlandii w celach zarobokowych. Pierwszego dnia chciałby zamieszkać w dowolnym mieście (miasto początkowe), a następnie udać się do wybranego miasta (miasto końcowe). Kupiec na drodze z jednego miasta do drugiego nie może dwa razy odwiedzić tego samego miasta, ze względu na przepisy prawne Bajtalndii. Chciałby jednak wybrać miasto początkowe i końcowe w taki sposób, aby jego zarobek był jak największy.
Kupiec zarabia poruszając się pomiędzy miastami. Dla każdego bezpośredniego połączenia wiemy, ile bajtalarów kupiec zarobi lub straci. Pomóż wybrać kupcowi dwa miasta tak, aby jego zarobek był jak największy (w szczególności miasto początkowe i końcowe może być tym samym miastem).
W pierwszej linii wejścia znajduje się jedna liczba całkowita (
). W następnych
wierszach po trzy liczby całkowite
(
), oznaczające, że istnieje bezpośrednie połączenie między miastami
i
, w którym kupiec zarobi
bajtalarów (ujemne
oznacza stratę kupca).
W pierwszym i jedynym wierszu wyjścia powinna znaleźć się jedna liczba cakłkowita oznaczająca maksymalny zarobek kupca.
Dla danych wejściowych:
6 1 3 3 3 2 2 4 3 2 3 5 -1 5 6 4
poprawną odpowiedzią jest:
6
Autor zadania: Jacek Tomasiewicz.