Беси расположена на сети из N (2≤N≤10
5) вершин помеченных 1…N и 2N порталов помеченных 1…2N. Каждый портал соединяет две различных вершины u и v (u≠v). Множество порталов может соединять некоторую пару вершин.
Каждая вершина v соседняя для четырёх различных порталов. Список порталов вершины v задаётся как pv=[p
v,1,p
v,2,p
v,3,p
v,4].
Ваше текущее положение может быть представлено упорядоченной парой (current vertex,current portal); то есть парой (v,p
v,i) где 1≤v≤N и 1≤i≤4. Вы можете использовать одну из следующих операций для изменения своего текущего положения:
Изменить текущую вершину перемещением через текущий портал.
Переключить текущий портал. В каждой вершине первые два портала в списке объединены в пару и последние два портала в списке также объединены в пару. Поэтому если Ваше текущее состояние (v,p
v,2), то Вы можете переключиться чтобы использовать портал (v,p
v,1) и обратно. Аналогично, если Ваше текущее положение (v,p
v,3) Вы можете переключиться на портал (v,p
v,4) и обратно. никакие другие переключения не разрешены (например, Вы не можете переключиться с портала pv,2 на портал) p
v,4).
Всего имеется 4N различных состояний. К несчастью, может не оказаться, что что любое состояние достижимо из любого с помощью последовательности заданных операций. Поэтому, за цену cv (1≤c
v≤1000) мунов вы можете сделать перестановку списка порталов соседних вершине v, в любом желаемом Вами порядке. После этого первые два портала в списке объединяются в одну пару, а последние два портала - в другую пару.
Например, если Вы переставить порталы вершины v в порядке [p
v,3,p
v,1,p
v,2,p
v,4], Это означает. что если Вы в вершине v,
Если Вы в портале p
v,1, Вы можете переключиться на портал p
v,3 и обратно
Если Вы в портале p
v,2, Вы можете переключиться на портал p
v,4 и обратно
Теперь Вы не можете переключаться с портала p
v,1 на p
v,2, или с портала p
v,3 на портал p
v,4 и обратно.
Вычислите минимальное количество мунов, требуемых для модификации сети таким образом, чтобы сделать достижимым каждое состояние из каждого состояния. Гарантируется, что тестовые данные сконструированы таким образом, что существует хотя бы один способ такой модификации сети.
Входные данные:
Первая строка содержит N.
Каждая из следующих N строк описывает вершину. Строка v+1 содержит 5 разделённых одиночными пробелами целых чисел c
v,p
v,1,p
v,2,p
v,3,p
v,4.
Гарантируется, что для каждой v все p
v,1,p
v,2,p
v,3,p
v,4 различны, и каждый портал появляется в списках ровно двух вершин.
Выходные данные:
Одна строка содержит минимальное количество мунов требуемых для модификации сети чтобы сделать возможным достижимость каждого состояния из другого состояния.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
5
10 1 4 8 9
11 1 2 5 6
12 9 10 2 3
3 4 3 6 7
15 10 8 7 5 |
13 |
Достаточно сделать перестановку списков вершин 1 и 4. Это требует c1+c4=13 мунов. Перестановки такие: p1=[1,9,4,8] и p4=[7,4,6,3]. |