W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Do mapy drogowej dołączona została dyskietka z tabelą długości najkrótszych dróg (odległości) między każdymi dwoma miastami na mapie. Wszystkie drogi są dwukierunkowe. Położenie miast na mapie ma następującą ciekawą własność. Jeżeli długość najkrótszej drogi z miasta do jest równa sumie długości najkrótszych dróg z do i z do , to miasto leży na (pewnej) najkrótszej drodze z do . Powiemy, że dwa miasta i sąsiadują ze sobą, jeżeli nie istnieje miasto takie, że długość najkrótszej drogi z miasta do jest równa długości najkrótszych dróg z do i z do .
Na podstawie danej tabeli odległości znajdź wszystkie pary miast sąsiadujących ze sobą.
Jeżeli tabela odległości ma postać
A B C A 0 1 2 B 1 0 3 C 2 3 0
wówczas sąsiednimi miastami są i oraz i .
Napisz program, który:
W pierwszym wierszu standardowego wejścia znajduje się liczba całkowita , . Jest to liczba miast na mapie. Miasta ponumerowane są jednoznacznie od do .
Tabela odległości jest zapisana w kolejnych wierszach. W wierszu , , jest zapisanych nieujemnych liczb całkowitych nie większych od , oddzielonych pojedynczym odstępem. Liczba -ta jest odległości między miastami oraz .
Twój program powinien wypisać na standardowe wyjście wszystkie pary (numerów) sąsiednich miast, po jednej parze w każdym wierszu. Każda para powinna pojawia się tylko raz. Liczby w parze powinny być uporządkowane rosnąco i oddzielone pojedynczym odstępem. Kolejność wypisywania par powinna być taka, że dla pary poprzedzającej parę , lub ( i ).
Dla danych wejściowych:
3 0 1 2 1 0 3 2 3 0
poprawną odpowiedzią jest:
1 2 1 3
Autor zadania: Piotr Chrząstowski-Wachtel.