eolymp
bolt
Try our new interface for solving problems
Məsələlər

Взлом сети

Взлом сети

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

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

КГБ хочет прослушивать все передаваемые в сети Пентагона сообщения. Для этого советскими программистами был разработан вирус, который, будучи установлен на какой-либо из компьютеров, передает КГБ всю информацию, проходящую через него. Оказалось, что материальные затраты, необходимые для установки вируса на различные компьютеры, различны. Требуется определить набор компьютеров, которые КГБ должно инфицировать, чтобы минимизировать общие материальные затраты.

Giriş verilənləri

Первая строка входного файла содержит N – количество компьютеров в сети (1N500). В i-й из последующих N строк содержатся номера компьютеров, с которыми непосредственно связан компьютер номер i. Далее следуют N целых чисел из диапазона [1, 1000] – материальные затраты, связанные с установкой вируса на каждый из компьютеров.

Çıxış verilənləri

В выходной файл выведите минимально возможные суммарные затраты.

Nümunə

Giriş verilənləri #1
10
10 3 0
7 10 0
1 6 9 0
5 0
4 10 0
3 0
2 8 0
7 0
3 0
1 2 5 0
1 2 3 10 100 100 7 100 100 5
Çıxış verilənləri #1
25