2090: 【入门】片区划分

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:1 解决:1

题目描述

A市有n个村庄(村庄编号为1~n),现准备将n个村庄划分为k个区(一个区中要有至少1个村庄),同一个区中的村庄要求有道路可以互相到达(不一定要直达,比如:A村要去C村,可以先先去B村,再去C村)。

为了节约成本,在划分之前,相关规划部门调研了村庄之间修路的成本,本次调研,共调研到了m条道路的建设成本。

假设所有村庄之间目前没有任何道路,如果要将n个村庄划分为k个区,请求出最少的修路成本?

输入

第一行有三个数n,m,k(1≤n≤1000,1≤m≤10000,1≤k≤10)

接下来m行每行三个数x,y,l,表示编号为x村到编号为y村修路的费用。(1≤x,y≤n,0≤l<10000)

测试数据保证x村到y村的道路只有1条。

输出

输出一个整数,代表最少的修路成本。
如果按照当前的调研数据,无法将n个村庄划分为k个区,请输出"No Answer"(比如,假设有5个村庄,只有2条道路的建设数据,是无法将5个村庄划分为2个区或者1个区的)。

样例输入 复制

3 1 2
1 2 1

样例输出 复制

1

提示

【样例解释】

1号村到2号村修路成本为1。

样例要求将3个村划分为2个区,只需要修1条路就可以将2个村合并为1个区,加上剩余的1个村,形成了2个区。

因此,样例中只需要在1号村和2号村之间修路,就可以实现划分2个区的目标。

来源/分类