#Pscc16. 2.通讯问题
2.通讯问题
2.通讯问题
题目描述
机关SERN截获了一条短信。SERN总部必须尽快将这个消息通过地下秘密通讯网络,传达到所有分部。
SERN共有N个部门(总部编号为),通讯网络有M条单向通讯线路,每条线路有一个固定的通讯花费。
消息的传递只能按照固定的方式进行:从一个已知消息的部门向另一个与它有线路相连的部门传递。我们定义总费用为所有部门传递消息的费用和。
幸运的是,如果两个部门可以直接或间接地相互传递消息(即能按照上述方法将信息由X传递到Y,同时能由Y传递到X),我们就可以忽略它们之间的花费。
SERN总部的工程师希望知道,达到目标的最小花费是多少。
输入格式
多组数据,文件以2个0结尾。
每组数据第一行,一个整数N,表示有N个包括总部的部门(从0开始编号)。然后是一个整数M,表示有M条单向通讯线路。
接下来M行,每行三个整数。
输出格式
每组数据一行,一个整数表示达到目标的最小花费。
数据范围
(原站未提供,导入后需人工补齐)
样例
3 3
0 1 100
1 2 50
0 2 100
3 3
0 1 100
1 2 50
2 1 100
2 2
0 1 50
0 1 100
0 0
150
100
50
提示
样例解释
第一组数据:总部把消息传给分部1,分部1再传给分部2。总费用:100+50=150。
第二组数据:总部把消息传给分部1,由于分部1和分部2可以互相传递消息,所以分部1可以无费用把消息传给2。总费用:100+0=100。
第三组数据:总部把消息传给分部1,最小费用为50。总费用:50
对于10%的数据,保证M=N-1。
对于另30%的数据,1<=N<=20,1<=M<=20。
对于100%的数据,1<=N<=5*10^4,1<=M<=10^5,1<=C_i<=10^5,1<=数据组数<=5。
数据保证一定可以将信息传递到所有部门。
。