#Pscc16. 2.通讯问题

    ID: 602 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 普及+/提高- 上传者: 标签>强连通分量赛制:OI来源:wyfoj http://127.0.0.1

2.通讯问题

2.通讯问题

题目描述

机关SERN截获了一条短信。SERN总部必须尽快将这个消息通过地下秘密通讯网络,传达到所有分部。

SERN共有N个部门(总部编号为),通讯网络有M条单向通讯线路,每条线路有一个固定的通讯花费cic_i。

消息的传递只能按照固定的方式进行:从一个已知消息的部门向另一个与它有线路相连的部门传递。我们定义总费用为所有部门传递消息的费用和。

幸运的是,如果两个部门可以直接或间接地相互传递消息(即能按照上述方法将信息由X传递到Y,同时能由Y传递到X),我们就可以忽略它们之间的花费。

SERN总部的工程师希望知道,达到目标的最小花费是多少。

输入格式

多组数据,文件以2个0结尾。

每组数据第一行,一个整数N,表示有N个包括总部的部门(从0开始编号)。然后是一个整数M,表示有M条单向通讯线路。

接下来M行,每行三个整数xi,yi,ci,表示第i条线路从xi连向yi,花费为cix_i,y_i,c_i,表示第i条线路从x_i连向y_i,花费为c_i。

输出格式

每组数据一行,一个整数表示达到目标的最小花费。

数据范围

(原站未提供,导入后需人工补齐)

样例

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。

数据保证一定可以将信息传递到所有部门。

。