题目描述

小Q非常喜欢旅游,在这个阳光明媚的夏天,他来到了一个美丽的海滨城市QD,在那里度过短暂的一个月假期顺便庆祝一下RQNOJ诞生三周年,然后就要乖乖回到学校好好学习了。QD这座城市,一共有N个旅游景点,可以供游客前来参观,每个景点都是那么的美丽,以至于他不想错过。QD还是一个交通非常发达的城市,一共有M条单向通行的道路,连接着各个旅游景点,但是,出现了一个让人比较头疼的问题,那就是QD的道路比较拥挤,经常会出现堵车的情况。为了便于旅游,小Q已经搜集到每条道路的拥挤情况Ki,Ki值越大表示这条道路越拥挤,小Q自然希望选择不拥挤的道路通行。

现在问题来了,小Q定义了一种游览方法:选取一个没有被访问的景点,从这个景点开始依次游览至少一个当前还没有被游览过的景点,最后从最后一个被游览的景点回到起始景点(即形成了一个圈),这代表着完成了一次游览。小Q希望通过若干次这种游览方法,把所有景点都游览一次。因为NOI小Q考囧了,之后连数都不会算了,所以请你帮小Q计算一下,所需要经过的道路的Ki之和,使所有和最小。

约定及数据规模:

对于30%的数据,N<=12

对于100%的数据,N<=100 M<=2*10^4,时限:1000ms,内存上限:256MB且保证数据有解。

样例说明:

小Q选择1号景点为第一次游览的起始景点,然后来到第2个景点,1-2这条道路拥挤值为1

从景点2又来到了3号景点,2-3这条道路拥挤值为2

从3号景点回到起始景点1,3-1这条道路拥挤值为3

第一次游览结束,已经浏览所有景点,所以不再执行第二次游览。

输入格式

第1行有两个正整数N,M,用空格隔开。

第2~M+1行,每行有3个整数u,v,k,表示有一条从景点u出发到景点v且拥挤情况为k的单向通行道路。

输出格式

输出共计1行。

第1行表示小Q游览这N个景点,所经过的道路的拥挤值之和的最小值。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论