Ограничения: время – 600ms/1200ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Зелье колдуньи Гингемы может иметь много злобных эффектов, а общая сила зелья вычисляется как сумма сил всех
отдельных эффектов. Каждый эффект может проявляться в зелье только 1 раз, поэтому при попытке добавления
к зелью эффекта, которое оно уже имеет, сила зелья не изменится.
Каждый из эффектов может вызываться определенным ингредиентом, добавленным в зелье. Но (колдовство — сложная штука!) один и тот
же ингредиент вызывает разные эффекты в зависимости от того, какой ингредиент добавлялся в зелье непосредственно
перед ним. Хуже того, если положить в зелье непосредственно друг за другом несовместимые ингредиенты — оно испортится и полностью потеряет свою силу.
Помогите Гингеме сварить зелье с максимальной возможной силой из заданного набора ингредиентов.
В первой строке ввода находятся два целых числа: `N` – количество ингредиентов (`1<=N<=10^5`) и `M` – количество возможных эффектов (`0<=M<=10^5`).
Затем следует `M` строк по три натуральных числа в каждой, описывающих возможные эффекты:
- `a_i` - номер ингредиента (`1<=a_i<=N`), вызывающего эффект;
- `p_i` – номер предшествующего ингредиента (`1<=p_i<=N, p_i!=a_i`), который должен быть положен в зелье непосредственно перед `a_i`-ым, чтобы эффект появился;
- `s_i` – сила эффекта (`1<=s_i<=10^9`).
Например, строка "2 1 10" означает: если добавить в зелье ингредиент 2 сразу после ингредиента 1, то он вызовет эффект с силой 10. Обратите внимание,
что пара "1 после 2" может быть несовместимой, даже если "2 после 1" приносит положительный эффект.
Любые пары ингредиентов, кроме `M` описанных, являются несовместимыми. Гарантируется, что добавление
одного и того же ингредиента два раза подряд не приносит эффекта, а одна и та же пара
ингредиентов встречается в описании не более 1 раза. Один и тот же ингредиент разрешается добавлять в
зелье несколько раз. Первый добавленный в зелье ингредиент (тот, перед которым ничего не добавлялось) никогда не
приносит самостоятельного эффекта.
Выведите одно целое число — максимальную силу зелья.
```sample Пример ввода 1
7 6
2 1 2
2 3 2
3 2 1
3 4 1
5 3 3
5 6 6
```
```sample Пример вывода 1
8
```
```sample Пример ввода 2
10 0
```
```sample Пример вывода 2
0
```
Пояснение к примеру 1: в первом случае можно добавлять ингредиенты в зелье в последовательности 1-2-3-2-3-5,
общая сила эффектов 2+1+2+0+3=8. Эффект «3 после 2» добавляется только 1 раз, при первом появлении соответствующей пары.
Компонент 7 не совместим ни с каким другим и его нельзя добавить в зелье, не испортив его.
Пояснение к примеру 2: все 10 ингредиентов несовместимы между собой. Из них нельзя сварить ни одного зелья с положительной силой.
Начало
Рабочее место участника
Динамическое программирование и запоминающие функции