Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
MWP3_2A1 - Korek |
Czy wiecie, że w rankingu najbardziej zakorkowanych miast Europy na pierwszym miejscu znajduje się Bruksela? Nie byłoby nic niepokojącego gdyby nie fakt, że miejsca 2 i 3 zajmują odpowiednio Warszawa i Wrocław. Jak już wiadomo najbliższe Akademickie Mistrzostwa Polski w Programowaniu Zespołowym odbędą się właśnie w Warszawie. Stan dróg tego miasta rodzi poważne obawy organizatorów. W związku z tym wystąpili oni z prośbą do Ciebie o napisanie programu, który na podstawie opisu sieci dróg oraz ilości samochodów na poszczególnych skrzyżowaniach obliczy najmniej zakorkowaną trasę z hotelu do miejsca, w którym odbędą się zawody.
Wejście
W pierwszej linii wejścia znajduje się jedna liczba naturalna Z (1 ≤ Z ≤ 10) określająca ilość zestawów danych. W kolejnych liniach znajdują się zestawy danych.
Pierwsza linia każdego zestawu danych zawiera cztery liczby całkowite n, m, a, b (1 ≤ n ≤ 1000; (n - 1) ≤ m ≤ (n × (n - 1)) / 2; 1 ≤ a, b ≤ n i a ≠ b) oznaczające odpowiednio ilość skrzyżowań i łączących je dróg oraz numer skrzyżowania początkowego i końcowego. W kolejnych m liniach znajduje się opis dróg łączących skrzyżowania. Opis każdej drogi składa się z czterech liczb całkowitych c, d, s, t (1 ≤ c, d ≤ n; 0 ≤ s ≤ 106; 1 ≤ t ≤ 2). Liczby c i d określają, że jest to droga łącząca skrzyżowania c i d. Liczba s określa stan zakorkowania drogi, zaś liczba t jej rodzaj: 1 - ulica jednokierunkowa, 2 - ulica dwukierunkowa. Zapis 5 8 100 2 oznacza, że skrzyżowanie 5 połączone jest z 8 dwukierunkową ulicą, a w korku stoi 100 samochodów. Dla uproszczenia zakładamy, że korek w obydwie strony jest takiej samej długości.
Wyjście
Dla każdego zestawu danych należy w osobnej linii wypisać jedną liczbę całkowitą określającą minimalną sumaryczną długość korka w jakim trzeba odstać, aby dojechać z punktu początkowego do końcowego.
Przykład
Wejście:
1 6 9 1 4 1 2 50 1 1 6 8 1 2 3 90 2 2 6 4 2 2 5 8 1 6 5 100 2 3 5 80 1 3 4 10 1 5 4 20 1
Wyjście:
40
Dodane przez: | Maciej Boniecki |
Data dodania: | 2010-12-08 |
Limit czasu wykonania programu: | 0.5s-4s |
Limit długości kodu źródłowego | 50000B |
Limit pamięci: | 1536MB |
Cluster: | Cube (Intel G860) |
Języki programowania: | All except: ASM64 JS-MONKEY SCM qobi |
Pochodzenie: | III Mistrzostwa WWSI w Programowaniu |