V Olimpiada Informatyczna 1997/98
|
Zadanie: SIE
|
Autor: Piotr Chrząstowski-Wachtel
|
II ETAP, SESJA PRÓBNA - CZWARTEK 12 LUTEGO 1998 r. |
Plik źródłowy: | SIE.??? (np. pas, c, cpp) |
Plik wykonywalny: | SIE.exe |
Plik wejściowy: | SIE.in |
Plik wyjściowy: | SIE.out |
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 A do B jest równa sumie długości najkrótszych dróg z A do C i z C do B, to miasto C leży na (pewnej) najkrótszej drodze z A do B. Powiemy, że dwa miasta A i B sąsiadują ze sobą, jeżeli nie istnieje miasto C takie, że długość najkrótszej drogi z miasta A do B jest równa długości najkrótszych dróg z A do C i z C do B. 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 | 0 | 3 |
Napisz program, który:
W pierwszym wierszu pliku wejściowego SIE.IN znajduje się
liczba całkowita n, 1<=n<200. Jest to liczba miast na mapie.
Miasta ponumerowane są jednoznacznie od 1 do n.
Tabela odległości jest zapisana w kolejnych n wierszach
pliku SIE.IN. W wierszu i+1, 1 <=i<=n, pliku SIE.IN jest
zapisanych n nieujemnych liczb całkowitych nie wiekszych od 200, oddzielonych pojedynczym odstępem. Liczba j-ta jest odległości między miastami i oraz j.
Twój program powinien wypisać w pliku wyjściowym SIE.OUT 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 (a,b) poprzedzającej parę (c,d), a < c lub (a=c i b < d).
PrzykładDla pliku tekstowego SIE.IN:
3 0 1 2 1 0 3 2 3 0
poprawnym rozwiązaniem jest plik wyjściowy SIE.OUT:
1 2 1 3