| Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
FR_07_19 - Sciezka |
Jasio po godzinach spędzonych z matematyką musi czasem od niej odpocząć. Lubi wtedy grać w gry MMORPG. Królowa nauk jest jednak obecna i tutaj. Jasio w swojej grze ma do wykonana kilka zadań (questów). Aby wykonać każdy z nich, trzeba odwiedzić kilka miejsc. Miejsca są ze sobą połączone, ale żeby dostać się z jednego do drugiego, trzeba zapłacić określoną kwotę. Można jednak wyznaczyć optymalną trasę między nimi, wykonując kilka zadań w jednym czasie. Pomóż Jasiowi i oblicz, jaką najmniejszą kwotę musi przygotować, by wykonać wszstkie zadania.
Input
Na początku zostaną podane dwie liczby: m(m<100) oznaczająca ilość wszystkich miejsc oraz s(s<300) oznaczająca ilość dostępnych ścieżek między nimi. W kolejnych m liniach na wczytanie będą czekać nazwy miejsc (nie występują w nich spacje i nazwa jest krótsza niż 35 znaków). Potem podanych będzie s linii zawierających informacje o ścieżkach: jakie miejsca łączą oraz jaki jest koszt podróży. W kolejnej linii znajduje się miejsce startowe. Na końcu wejścia do wczytania będzie od 1 do 3 linii. Każda z nich to zadanie złożone z nieokreśclonej liczby miejsc do odwiedzenia, jednak łączna ich ilość nie przekracza 50.
Output
Na wyściu ma znaleźć się jedna liczba oznaczająca kwotę potrzebną do wykonania wszystkich zadań.
Example
Input: 10 31 Town_of_Schuttgart Town_of_Goddard Rune_Township Town_of_Aden Town_of_Oren Town_of_Giran Town_of_Dion Town_of_Gludio Gludin_Village Heine Town_of_Schuttgart Town_of_Goddard 10000 Town_of_Goddard Rune_Township 10000 Town_of_Goddard Town_of_Aden 8100 Town_of_Goddard Town_of_Schuttgart 10000 Rune_Township Town_of_Goddard 10000 Rune_Township Town_of_Oren 10000 Rune_Township Town_of_Aden 37000 Town_of_Aden Town_of_Goddard 8100 Town_of_Aden Rune_Township 37000 Town_of_Aden Town_of_Oren 6900 Town_of_Aden Hunters_Village 5900 Town_of_Aden Town_of_Oren 6900 Town_of_Aden Town_of_Giran 13000 Town_of_Oren Town_of_Aden 6900 Town_of_Oren Rune_Township 10000 Town_of_Oren Hunters_Village 4100 Town_of_Oren Town_of_Giran 9400 Hunters_Village Town_of_Oren 4100 Hunters_Village Town_of_Aden 5900 Town_of_Giran Town_of_Aden 13000 Town_of_Giran Town_of_Oren 9400 Town_of_Giran Town_of_Gludio 29000 Town_of_Giran Town_of_Dion 6800 Town_of_Giran Heine 7600 Heine Town_of_Giran 7600 Heine Town_of_Dion 12000 Town_of_Dion Heine 12000 Town_of_Dion Town_of_Giran 6800 Town_of_Dion Town_of_Gludio 3400 Town_of_Gludio Gludin_Village 7300 Gludin_Village Town_of_Gludio 7300 Town_of_Goddard Town_of_Gludio Town_of_Oren Town_of_Schuttgart Heine Town_of_Oren Gludin_Village Gludin_Village Rune_Township Town_of_OrenOutput:
100400
| Dodane przez: | Adrian Piórkowski |
| Data dodania: | 2017-04-07 |
| Limit czasu wykonania programu: | 1s |
| Limit długości kodu źródłowego | 50000B |
| Limit pamięci: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Języki programowania: | All except: ASM32-GCC COBOL D-CLANG D-DMD ELIXIR FANTOM GOSU GRV JS-MONKEY NIM OBJC OBJC-CLANG PICO RUST SCM qobi CHICKEN VB.NET |
ukryj komentarze
|
2017-05-13 23:19:15
Chciałbym zwrócić uwagę, że np. Hunters_Village nie jest wymienione na początku w nawzwach miejsc, a potem występuje w informacjach o ścieżkach - czy jest to celowe ? |
RSS