Философы долго размышляли над проблемой Троллейбуса . К сожалению, ни один человек еще не решил эту проблему. К счастью, как программисты мы можем использовать компьютеры, чтобы решить эту проблему для нас!

вход

Ваша программа будет принимать в качестве входных данных (конечный) ориентированный граф (с не более чем одним ребром от xдо y, для любого xи y), с указанным узлом и неотрицательным целым числом, прикрепленным к каждому ребру (представляющее количество людей, привязанных к этому треку) , Кроме того, каждый узел имеет хотя бы один выходной край.

Тележка запускается в обозначенном узле. Каждый ход, если тележка находится в узле x, утилитарист выбирает ребро (x,y). Люди на этом краю умирают, а троллейбус сейчас на краю y. Этот процесс продолжается вечно.

Обратите внимание , что люди могут только умереть один раз, поэтому , если ребро (x,y)имеет nчеловек , привязанные к ней, а тележка работает над ними, скажем, в 100 раз, он все равно будет только привести к nсмерти.

Выход

Утилитарист делает свой выбор таким образом, чтобы минимизировать число людей, которые умирают (что гарантированно будет конечным, поскольку есть только конечные люди). Ваша программа выведет этот номер.

Формат ввода

Вы можете использовать входной граф любым разумным способом. Например, вы можете взять его в качестве матрицы и считать назначенный узел как узел с меткой 0. Или вы можете использовать что-то вроде x1,y1,n1;x2,y2,n2;.... Например, 0,a,0;a,b,5;a,c,1;b,b,0;c,c,0чтобы представить стандартную задачу тележки (с петлями в конце).

Testcases

• 0,a,0;a,b,5;a,c,1;b,b,0;c,c,0 -> 1 (перейдите от 0 к a, a к c (убив одного человека), а затем продолжайте вращать тележку от c до c).
• 0,0,1;0,a,5;a,a,0 -> 1 (продолжайте идти от 0 до 0, работая над 1 человеком всю вечность),
• 0,a,5;0,b,1;a,a,1;b,b,6 -> 6 (0 -> a -> a -> a -> a -> ... (обратите внимание, что жадное решение перехода к b было бы неверным))
• 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 (обратите внимание, что утилитарист может использовать два разных варианта: оба убивают только одного человека)

Это код-гольф , поэтому выигрывает самый короткий ответ! Удачи.

Примечания: не будет больных петель, а многодорожечный дрифтинг запрещен. Кроме того, хотя я предпочитаю думать об этой проблеме с точки зрения трех законов Азимова, Питер Тейлор отметил в песочнице, что эта проблема математически эквивалентна проблеме поиска ро (пути, по которому петли возвращаются назад) самого низкого веса ,

Желе , 27 23 байта

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

Попробуйте онлайн! (последний контрольный пример)

Жестокая версия (Изуродовать большинство людей)

Принимает ввод в виде чисел. Для последнего примера 1есть aи 2есть b. 0это начальный узел. Первый аргумент - это список ребер (например [0,1],[0,2],[1,1],[2,2]), а второй аргумент - это список ребер и количество людей на них (например [[0,1],[0,2],[1,1],[2,2]],[1,1,0,0]).

Как это устроено

ṗ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 байт

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])

Попробуйте онлайн!

Принимает ввод как словарь с ключом по идентификатору узла. Записи представляют собой словарь соседей и количество людей на дорожке между узлом и соседом. Например, для первого теста:

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

0 - начальный узел, 1 - узел «а», 2 - узел «б» и т. Д.

Perl 6 , 90 74 байта

Спасибо Джо Кингу за -16 байтов.

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

Порт Pyot-решения RootTwo .

Попробуйте онлайн!