Problem 3 - „Koleje”
W pewnym postępowym kraju od stuleci rozwija się transport kolejowy. Początkowo połączenia
kolejowe obejmowały tylko największe i najszybciej rozwijające się miasta, a prędkość pociągów
pozostawiała wiele do życzenia. Według opowieści starszych można było wyskoczyć na grzyby,
gdy pociąg przejeżdżał przez las, by po grzybobraniu załapać się jeszcze do ostatniego wagonu. Z
czasem prędkości pociągów rosły, by w końcu doprowadzić do likwidacji konwencjonalnych
przejazdów kolejowych (ze względów bezpieczeństwa). Zmienił się też wygląd pociągów –
początkowo przypominały fabryki z kominem, a obecnie bliżej im do filmów SF. W kraju tym nie
toleruje się obniżenia prędkości pociągów i po modernizacji danego odcinka średnia prędkość na
nim może jedynie wzrosnąć. Co więcej, postój na każdej stacji wynosi 5 minut i nigdy nie ma
opóźnień, a z żadnego miasta nie wychodzi więcej niż 50 połączeń. W bazie danych kolei istnieje
całe archiwum dotyczące budowy i modernizacji odcinków łączących poszczególne miasta.
Zlecono napisanie oprogramowania do analizy tych danych. Twoim zadaniem jest ustalenie, kiedy
czas przejazdu pociągiem między zadaną parą miast skrócił się do zadanego poziomu.
Wejście:
W pierwszej linii wejścia podane są trzy liczby całkowite n, m i z (1<=n<=10000,1<=m<=100000,
1<=z<=10) oznaczające odpowiednio liczbę miast, liczbę budowanych/modernizowanych
odcinków oraz liczbę zapytań do programu. W kolejnych m liniach znajdują się chronologiczne
informacje dotyczące budowy. W każdej z tych linii podane są: data (format rrrr-mm-dd), następnie
znak 'm' lub 'b' w zależności od tego czy chodzi o budowę (połączenie wcześniej nie istniało) czy o
modernizację istniejącego już odcinka, następnie para różnych miast m1, m2 (1<=m1, m2<=n)
między którymi budowane/modernizowane jest połączenie, a następnie średnią prędkość v (w km/h)
na tym odcinku (1<=v<=500) oraz (w przypadku budowy) również długość d (w km) nowobudowanego
połączenia (1<=d<=1000). v i d są liczbami całkowitymi i 60*d mod v = 0. W
kolejnych z liniach znajdują się zapytania złożone z liczb m1, m2, c (1<=m1, m2<=n,
1<=c<=10000) oznaczających parę miast oraz maks. czas połączenia między nimi (w minutach).
Wyjście:
W z liniach wyjścia należy odpowiedzieć na zapytania: kiedy po raz pierwszy udało się osiągnąć
czas najszybszego połączenia (pośredniego lub bezpośredniego) między danymi miastami nie
przekraczający zadanego limitu. Jeśli taki czas nie został dotąd osiągnięty, należy wypisać 'NIE'.
Przykład:
Wejście:
5 10 3 //5 miast, 10 połączeń, 3 zapytania
1900-05-30 b 1 2 30 60 //budowane połączenie między miastami 1 i 2, v=30 km/h, d=60 km
1900-07-15 b 2 5 40 120 //itd.
1905-04-19 b 1 4 35 70
1910-06-03 b 4 5 50 100
1950-10-25 m 2 5 72 //modernizowane połączenie między miastami 2 i 5: nowe v=72 km/h
1955-01-31 b 1 3 60 90
1990-12-12 b 3 5 180 90
2000-09-20 b 3 4 240 60
2005-06-14 m 1 4 280 //itd.
2008-03-07 b 2 3 150 50
1 5 230 //Kiedy pomiędzy miastami 1 i 5 osiągnięto czas podróży maks. 230 minut
1 5 75 //itd.
2 4 35
Wyjście:
1950-10-25 //od 1950-10-25 między miastami 1 i 5 dało się przejechać w 225 minut (<=230)
2005-06-14 //od 2005-06-14 między miastami 1 i 5 dało się przejechać w 70 minut (<=75)
NIE //najszybsze połączenie między 2 i 4 wymaga obecnie 40 minut

Na podstawie zadania napisałem program który nie działa do końca poprawnie dla duzych testow. Czy znalazłaby się osoba chętna do pomocy?