RYIP在线题库
首 页   >   习题练习   >   提交
Problem2193--纯美骑士团

2193: 纯美骑士团

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

【 Description 】

在宇宙中,有着这么一个团体——他们巡游整个宇宙,宣扬【纯美】女神——伊德莉拉的美貌,名为“【纯美】骑士团”。这个团伙中,绝大多数都是纯美骑士团授勋骑士,虽然共同信奉伊德莉拉女神的容貌,但因为信仰方式不同,授勋骑士彼此之间很少交流,很多骑士只有除自己外极个别纯美骑士的联络方式(双方均可以联络对方),因为涉及到宇宙级别,所以即使要联系,成本也十分昂贵,但如果遇到关键情况,某个纯美骑士会需要联络其他纯美骑士,但又不想耗费太多成本。怎么办呢?
已知:这个骑士团有n个骑士,期间m组骑士(每组两个骑士,可以互相发送消息),某两个拥有联系方式的纯美骑士联系代价为z元
今天,有一位纯美骑士发现了一件重要的事情,他现在需要通知整个【纯美】骑士团的所有纯美骑士。但需要考虑资金问题,他决定利用最划算的通知方法。要求:需要所有的纯美骑士都接收到通知,可以由任何一位纯美骑士向可以取得联系的另一位纯美骑士发送信息;取消耗资金最少的方法;

【 Input 】

第一行为两个正整数n和m,意思如上(n,m<=20)
接下来m行,每行三个正整数x,y,z(0<=z<=100),表示纯美骑士x和纯美骑士y之间联络需要花费z的成本代价

【 Output 】

一行一个正整数输出最节省成本的联络方法所需的成本

【 Sample Input 】

10 10
1 2 1
1 3 2
1 4 3
1 5 4
1 6 5
1 7 6
1 8 7
1 9 8
1 10 9
9 10 1

【 Sample Output 】

37

【HINT】

【样例解释】:
由1号纯美骑士向第1~9号发送消息,最后由9号纯美骑士向10号纯美骑士发送信息,共耗费1+2+3+4+5+6+7+8+1=37的成本


【提示】:
接受到消息的纯美骑士就可以发送给其他纯美骑士消息

【 Source/Category 】