Задача на графы C++

Ребенок нарисовал кружки и некоторые из них соединил отрезками. Кружки он пометил целыми числами от 1 до N, а на каждом отрезке поставил стрелочку. Затем он приписал каждому кружочку вес в виде некоторого целого числа и определил начальный и конечный кружочки. Из первого он должен выйти, а во второй попасть.

Ребенок решил для себя следующее:

набрать максимально возможное суммарное количество очков;

по каждому отрезку пройти ровно один раз;

если в кружок он попадает при движении по направлению стрелки, то к суммарному количеству очков вес этого кружка прибавляется;

если в кружок он попадает при движении против направления стрелки, то из суммарного количества очков вес этого кружка вычитается.