Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
974. Roads
Олимпиадные задачи на английском языке| 03/07/2008 | Лето 2008 дорешивание ( 5J) |
| 11/07/2008 | Лето 2008 - 5 (J) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
In a country there are `N` cities connected by `M` one way roads. You can paint any of these roads. To paint a road it costs `D` unit of money where `D` is the length of that road. Your task is to paint some of the roads so that the painted roads can be partitioned into some disjoint cycles such that every vertex appears in exactly `K` of these disjoint cycles. But you have to minimize the costs of painting these roads.
Input
Input starts with a line containing 3 integers `N` (`1\ ≤\ N\ ≤\ 40`), `M` (`1\ ≤\ M\ ≤\ 2000`) and `K` (`1\ ≤\ K`, `1\ ≤\ K*N\ ≤100`). Next lines contain description of `M` roads. Each description contains three integers `s`, `t` (`1\ ≤\ s,\ t\ ≤\ N`, `s\ ≠\ t`) and `D` (`0\ ≤\ D\ <\ 100`). That means there is a road of `D` length from city `s` to city `t`. You can assume that there will be at most one road in one direction between two cities.
Output
Output contains one integer denoting the minimum unit of money needed to paint roads. In the case it is impossible to paint the roads maintaining the constraints output `-1`.
Sample Input 1
4 8 1 1 2 1 2 1 2 3 4 1 4 3 2 1 3 5 3 1 6 2 4 5 4 2 6
Sample Output 1
6
Sample Input 2
4 8 1 1 2 1 2 1 10 3 4 10 4 3 1 1 3 10 3 1 1 2 4 1 4 2 10
Sample Output 2
4
Sample Input 3
4 8 2 1 2 1 2 1 2 3 4 1 4 3 2 1 3 5 3 1 6 2 4 5 4 2 6
Sample Output 3
28
Sample Input 4
3 4 1 1 2 5 2 1 6 1 3 7 3 1 8
Sample Output 4
-1
