시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 0 | 0 | 0 | 0.000% |
Firma SuperKurier oferuje dostarczanie przesyłek w dowolny zakątek świata. Firma ma sieć n placówek ponumerowanych od 1 do n. W placówkach następuje zbieranie przesyłek z określonego obszaru, ich sortowanie, przeładunek oraz dostarczanie odbiorcom. Pomiędzy placówkami utrzymywane są stałe połączenia umożliwiające transport przesyłek. Placówki podzielone są na klasy A, B i C. W sieci znajduje się nA placówek klasy A, nB placówek klasy B oraz nC placówek klasy C, przy czym nA + nB + nC = n, nA > 0, nC > 0. W placówkach klasy A odbywa się sortowanie zasadnicze oraz przeładunek przesyłek. Każda przesyłka na swej drodze od nadawcy do odbiorcy musi przejść przez co najmniej jedną placówkę klasy A. Placówki klasy A mają połączenia ze wszystkimi pozostałymi placówkami klasy A oraz z pewną liczbą placówek klasy B i C. W placówkach klasy B odbywa się sortowanie wtórne oraz przeładunek przesyłek. Każda placówka klasy B ma połączenia z co najmniej jedną placówką klasy A oraz z pewną liczbą placówek klasy C, nie ma natomiast połączeń z innymi placówkami klasy B. Zadaniem placówek klasy C jest jedynie odbieranie przesyłek z określonego obszaru i dostarczanie przesyłek do odbiorców na tym obszarze. Każda placówka klasy C ma tylko jedno połączenie z placówką klasy A lub B. Poniższy rysunek przedstawia przykładową sieć placówek.
Rysunek: Przykładowa sieć placówek.
Placówkom oraz połączeniom są przyporządkowane pary atrybutów (koszt, czas). Dla placówek para ta wyznacza koszt oraz czas odebrania lub doręczenia przesyłki na obszarze obsługiwanym przez placówkę, a także sortowania i przeładunku przesyłek, w zależności od klasy placówki. Para atrybutów przypisana połączeniu oznacza koszt i czas przewiezienia przesyłki pomiędzy placówkami.
Zadanie polega na wyznaczeniu dla danej sieci najlepszych tras transportu przesyłek z danej placówki początkowej s, do danej placówki docelowej t (placówki s i t są klasy C). Każda trasa charakteryzuje się parą atrybutów, kosztem oraz czasem transportu: są to sumy kosztów i czasów, placówek i połączeń znajdujących się na trasie (łącznie z s i t). Im mniejszy koszt i krótszy czas transportu, tym lepiej. Powiemy, że jedna trasa jest lepsza od drugiej, jeśli charakteryzuje się:
Interesują nas takie trasy, od których nie ma lepszych.
Na przykład, niech s = C1 oraz t = C2 (por. rysunek). Chcąc wybrać najlepsze trasy transportu przesyłek pomiędzy tymi placówkami rozważamy następujące trasy: C1 → B4 → A3 → B4 → C2, C1 → B4 → A6 → B4 → C2, C1 → B4 → A3 → A6 → B4 → C2 oraz C1 → B4 → A6 → A3 → B4 → C2 o parach (koszt, czas) odpowiednio: (55, 66), (60, 65), (84, 95) i (84, 95). Pierwsze dwie trasy są lepsze niż trzecia i czwarta. Tak więc, mamy dwie trasy transportu przesyłek, od których nie ma lepszych: C1 → B4 → A3 → B4 → C2 i C1 → B4 → A6 → B4 → C2.
Napisz program, który:
W pierwszym wierszu zapisane są dwie dodatnie liczby całkowite oddzielone pojedynczym odstępem: liczba placówek n oraz liczba połączeń m, 2 ≤ n ≤ 1000, 1 ≤ m ≤ 5000. Placówki są ponumerowane od 1 do n. W kolejnych n wierszach opisane są kolejne placówki, po jednej w wierszu. Opis każdej placówki składa się z litery A
, B
lub C
, oraz dwóch dodatnich liczb całkowitych k i c, pooddzielanych pojedynczymi odstępami. Liczba k oznacza koszt, a c czas sortowania przesyłek w placówce, 1 ≤ k ≤ 20, 1 ≤ c ≤ 20.
W kolejnych m wierszach opisane są połączenia między placówkami, po jednym w wierszu. Opis każdego z połączeń składa się z czterech liczb całkowitych a, b, k i c, pooddzielanych pojedynczymi odstępami. Liczby a i b, to numery połączonych placówek, 1 ≤ a, b ≤ n. Liczba k to koszt, a c to czas transportu przesyłki danym połączeniem, 1 ≤ k ≤ 100, 1 ≤ c ≤ 100. Wszystkie połączenia są dwukierunkowe. Między każdymi dwiema placówkami mamy co najwyżej jedno (bezpośrednie) połączenie.
W ostatnim wierszu zapisane są dwie dodatnie liczby całkowite s i t, oddzielone pojedynczym odstępem, 1 ≤ s, t ≤ n. Są to numery placówek początkowej i docelowej.
W pierwszym wierszu powinna zostać wypisana jedna dodatnia liczba całkowita r - liczba różnych par (koszt, czas) charakteryzujących wszystkie trasy transportu przesyłek z placówki s do t, od których nie ma lepszych. W kolejnych r wierszach powinny być wypisane te pary, w kolejności rosnących kosztów. Każda para powinna być wypisana w osobnym wierszu, a koszt i czas powinny być oddzielone pojedynczym odstępem.
9 9 C 1 2 C 2 1 A 20 30 B 12 13 C 1 1 A 23 27 B 10 15 C 1 3 C 3 2 1 4 1 1 2 4 1 2 3 4 3 2 5 3 2 7 3 6 5 1 6 4 4 3 6 7 4 4 7 8 3 3 7 9 2 2 1 2
2 55 66 60 65
Contest > Algorithmic Engagements > PA 2005 6-3번