printРабочее место участника

printЗадачи

974. Roads

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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
Source: Весенний турнир имени Мартовского зайца, 2007, ICPC Dhaka Asia RC, 2006
loading