Filozofowie od dawna zastanawiają się nad problemem wózka . Niestety, żaden człowiek nie rozwiązał jeszcze tego problemu. Na szczęście jako programiści możemy używać komputerów, aby rozwiązać za nas problem!

Wejście

Twój program weźmie na wejściu (skończony) wykres kierowany (z co najwyżej jedną krawędzią od xdo y, dla dowolnego xi y), z wyznaczonym węzłem i nieujemną liczbą całkowitą dołączoną do każdej krawędzi (reprezentującą liczbę osób związanych z tą ścieżką) . Ponadto każdy węzeł ma co najmniej jedną krawędź wyjściową.

Wózek rozpoczyna się w wyznaczonym węźle. W każdym zakręcie, jeśli wózek jest w węźle x, utylitarysta wybiera krawędź (x,y). Ludzie na tym brzegu umierają, a wózek jest teraz na krawędzi y. Ten proces trwa wiecznie.

Zauważ, że ludzie mogą umrzeć tylko raz, więc jeśli krawędź (x,y)ma nludzi przywiązanych do niej, a wózek przejeżdża nad nimi, powiedzmy 100 razy, nadal spowoduje to nśmierć.

Wynik

Utylitarysta dokonuje swoich wyborów w taki sposób, aby zminimalizować liczbę umierających ludzi (co gwarantuje, że są skończone, ponieważ są tylko ludzie skończeni). Twój program wyświetli ten numer.

Format wejściowy

Możesz wziąć wykres wejściowy w dowolny rozsądny sposób. Na przykład możesz wziąć to jako macierz i policzyć wyznaczony węzeł jako oznaczony jako 0. Lub możesz użyć czegoś takiego x1,y1,n1;x2,y2,n2;.... Na przykład w 0,a,0;a,b,5;a,c,1;b,b,0;c,c,0celu przedstawienia standardowego problemu z wózkiem (z pętlami na końcu).

Przypadki testowe

• 0,a,0;a,b,5;a,c,1;b,b,0;c,c,0 -> 1 (Przejdź od 0 do a, od a do c (zabijając jedną osobę), a następnie zapętlaj wózek od c do c).
• 0,0,1;0,a,5;a,a,0 -> 1 (Kontynuuj od 0 do 0, biegając przez 1 osobę na całą wieczność),
• 0,a,5;0,b,1;a,a,1;b,b,6 -> 6 (0 -> a -> a -> a -> a -> ... (zwróć uwagę, że chciwe rozwiązanie przejścia na b byłoby nieprawidłowe))
• 0,a,1;0,b,5;a,b,1;b,a,1 -> 3 (0 -> a -> b -> a -> b -> ...)
• 0,a,1;0,b,1;a,a,0;b,b,0 -> 1 (Zauważ, że istnieją dwie różne opcje, które utylitarysta może wziąć, aby zabić tylko jedną osobę)

To jest golf golfowy , więc wygrywa najkrótsza odpowiedź! Powodzenia.

Uwagi: Nie będzie żadnych zwolnień pętli, a dryfowanie wielościeżkowe jest zabronione. Ponadto, chociaż wolę myśleć o tym problemie w kategoriach trzech praw (-ów) Asimova, Peter Taylor zauważył w piaskownicy, że problem ten jest matematycznie równoważny z problemem znalezienia rho (ścieżki powrotnej do siebie) o najniższej wadze .

Galaretka , 27 23 bajtów

ṗL$µṭ0FIm2ASµÐḟµQ⁴ySµ€Ṃ

Wypróbuj online! (ostatni przypadek testowy)

Okrutna wersja (Okalecz najwięcej ludzi)

Pobiera dane wejściowe jako liczby. W ostatnim przykładzie 1jest ai 2jest b. 0jest węzłem początkowym. Pierwszy argument to lista krawędzi (np. [0,1],[0,2],[1,1],[2,2]), A drugi argument to lista krawędzi i liczby osób na nich (np [[0,1],[0,2],[1,1],[2,2]],[1,1,0,0].).

Jak to działa

ṗL$µṭ0FIm2ASµÐḟµQ⁴ySµ€Ṃ
ṗL$                       - on the first argument, get the Cartesian power of it to its length.
                            this gives all paths of the length of the input. Cycles are implicit
   µ        µÐḟ           - get valid paths starting with 0 -- filter by:
    ṭ0                      - prepend 0
      F                     - flatten
       I                    - get the difference between elements
        m2                  - every second difference: 0 for each edge that starts at the node the previous edge ended at, nonzero otherwise.
          AS                - 0 iff all elements are 0
               µ    µ€    - on each path:
                Q           - remove repeat edges.
                 ⁴y         - translate according to the mapping in the second program argument
                   S        - Sum
                      Ṃ   - get the minimum of these.

Python 3 , 80 bajtów

y=lambda d,s=0,p=[],f=0:f in p and s or min(y(d,s+d[f][t],p+[f],t)for t in d[f])

Wypróbuj online!

Pobiera dane wejściowe jako słownik wpisany przez identyfikator węzła. Wpisy to słownik sąsiadów i liczby osób na ścieżce między węzłem a sąsiadem. Na przykład dla pierwszego przypadku testowego:

{0: {1: 0}, 1: {2: 5, 3: 1}, 2: {2: 0}, 3: {3: 0}}

0 to węzeł początkowy, 1 to węzeł „a”, 2 to węzeł „b” itp.

Perl 6 , 90 74 bajtów

Dzięki Jo King za -16 bajtów.

my&g=->\a,\b=0,\c=@,\d=0 {a{d}&&b||min map {g a,b+$^f,(|c,d),$^e},a{d}.kv}

Rozwiązanie Port RootTwo w języku Python .

Wypróbuj online!