你是賽車比賽的負責人員,已經確定下次比賽將在某個城鎮舉辦比賽;標準的比賽路線為起點與終點相同,每個路段在比賽路線中只能被使用一次,且只有一個方向能用,而這個比賽路線當天才會公布。
城鎮路線錯綜複雜,每條路段與路段之間的交接處以 $1, \cdots, n$ 編號,且其中共有 $m$ 條路。
為了防止選手們賽前在城鎮中進行非法訓練,城鎮中每個路段都能架設監視器以捕捉犯規者。
但不同路段有不同的架設成本,且由於經費要盡量節省,所以要以最低的成本架設監視器。
第一列有 $n, m$ 表示路間有幾個交接處,以及有幾條路段 $(1\le n\le 10^ 4, 1\le m \le 10^ 5)$。
接著有 $m$ 列 $a, b, c$ 以表示交接處 $a$ 與 $b$ 之間有路段且裝監視器的成本為 $c\ (1\le a, b \le n, 1\le c \le 1000)$。
輸入保證城鎮是個連通圖,畢竟當代(?)賽車比賽得是連通的。
輸出裝設監視器的最低總成本。
第一筆範例以圖例表示為
點上數字為交接處編號,邊上數字為裝設監視器的成本
而最低成本 $6 = 3 + 3$ 為在路段 $(2, 3), (2, 5)$ 裝設監視器
在這兩處裝攝影機,這樣不管在何處出發然後回到起點,都能被監視器捕捉到
UVa Online Judge 1234 RACING
No. | Testdata Range | Score |
---|---|---|
1 | 0~119 | 100 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 50 | 65536 | 65536 | |
1 | 50 | 65536 | 65536 | |
2 | 50 | 65536 | 65536 | |
3 | 50 | 65536 | 65536 | |
4 | 50 | 65536 | 65536 | |
5 | 50 | 65536 | 65536 | |
6 | 50 | 65536 | 65536 | |
7 | 50 | 65536 | 65536 | |
8 | 50 | 65536 | 65536 | |
9 | 50 | 65536 | 65536 | |
10 | 50 | 65536 | 65536 | |
11 | 50 | 65536 | 65536 | |
12 | 50 | 65536 | 65536 | |
13 | 50 | 65536 | 65536 | |
14 | 50 | 65536 | 65536 | |
15 | 50 | 65536 | 65536 | |
16 | 50 | 65536 | 65536 | |
17 | 50 | 65536 | 65536 | |
18 | 50 | 65536 | 65536 | |
19 | 50 | 65536 | 65536 | |
20 | 50 | 65536 | 65536 | |
21 | 50 | 65536 | 65536 | |
22 | 50 | 65536 | 65536 | |
23 | 50 | 65536 | 65536 | |
24 | 50 | 65536 | 65536 | |
25 | 50 | 65536 | 65536 | |
26 | 50 | 65536 | 65536 | |
27 | 50 | 65536 | 65536 | |
28 | 50 | 65536 | 65536 | |
29 | 50 | 65536 | 65536 | |
30 | 50 | 65536 | 65536 | |
31 | 50 | 65536 | 65536 | |
32 | 50 | 65536 | 65536 | |
33 | 50 | 65536 | 65536 | |
34 | 50 | 65536 | 65536 | |
35 | 50 | 65536 | 65536 | |
36 | 50 | 65536 | 65536 | |
37 | 50 | 65536 | 65536 | |
38 | 50 | 65536 | 65536 | |
39 | 50 | 65536 | 65536 | |
40 | 50 | 65536 | 65536 | |
41 | 50 | 65536 | 65536 | |
42 | 50 | 65536 | 65536 | |
43 | 50 | 65536 | 65536 | |
44 | 50 | 65536 | 65536 | |
45 | 50 | 65536 | 65536 | |
46 | 50 | 65536 | 65536 | |
47 | 50 | 65536 | 65536 | |
48 | 50 | 65536 | 65536 | |
49 | 50 | 65536 | 65536 | |
50 | 50 | 65536 | 65536 | |
51 | 50 | 65536 | 65536 | |
52 | 50 | 65536 | 65536 | |
53 | 50 | 65536 | 65536 | |
54 | 50 | 65536 | 65536 | |
55 | 50 | 65536 | 65536 | |
56 | 50 | 65536 | 65536 | |
57 | 50 | 65536 | 65536 | |
58 | 50 | 65536 | 65536 | |
59 | 50 | 65536 | 65536 | |
60 | 50 | 65536 | 65536 | |
61 | 50 | 65536 | 65536 | |
62 | 50 | 65536 | 65536 | |
63 | 50 | 65536 | 65536 | |
64 | 50 | 65536 | 65536 | |
65 | 50 | 65536 | 65536 | |
66 | 50 | 65536 | 65536 | |
67 | 50 | 65536 | 65536 | |
68 | 50 | 65536 | 65536 | |
69 | 50 | 65536 | 65536 | |
70 | 50 | 65536 | 65536 | |
71 | 50 | 65536 | 65536 | |
72 | 50 | 65536 | 65536 | |
73 | 50 | 65536 | 65536 | |
74 | 50 | 65536 | 65536 | |
75 | 50 | 65536 | 65536 | |
76 | 50 | 65536 | 65536 | |
77 | 50 | 65536 | 65536 | |
78 | 50 | 65536 | 65536 | |
79 | 50 | 65536 | 65536 | |
80 | 50 | 65536 | 65536 | |
81 | 50 | 65536 | 65536 | |
82 | 50 | 65536 | 65536 | |
83 | 50 | 65536 | 65536 | |
84 | 50 | 65536 | 65536 | |
85 | 50 | 65536 | 65536 | |
86 | 50 | 65536 | 65536 | |
87 | 50 | 65536 | 65536 | |
88 | 50 | 65536 | 65536 | |
89 | 50 | 65536 | 65536 | |
90 | 50 | 65536 | 65536 | |
91 | 50 | 65536 | 65536 | |
92 | 50 | 65536 | 65536 | |
93 | 50 | 65536 | 65536 | |
94 | 50 | 65536 | 65536 | |
95 | 50 | 65536 | 65536 | |
96 | 50 | 65536 | 65536 | |
97 | 50 | 65536 | 65536 | |
98 | 50 | 65536 | 65536 | |
99 | 50 | 65536 | 65536 | |
100 | 500 | 65536 | 65536 | |
101 | 500 | 65536 | 65536 | |
102 | 500 | 65536 | 65536 | |
103 | 500 | 65536 | 65536 | |
104 | 500 | 65536 | 65536 | |
105 | 500 | 65536 | 65536 | |
106 | 500 | 65536 | 65536 | |
107 | 500 | 65536 | 65536 | |
108 | 500 | 65536 | 65536 | |
109 | 500 | 65536 | 65536 | |
110 | 500 | 65536 | 65536 | |
111 | 500 | 65536 | 65536 | |
112 | 500 | 65536 | 65536 | |
113 | 500 | 65536 | 65536 | |
114 | 500 | 65536 | 65536 | |
115 | 500 | 65536 | 65536 | |
116 | 500 | 65536 | 65536 | |
117 | 500 | 65536 | 65536 | |
118 | 500 | 65536 | 65536 | |
119 | 500 | 65536 | 65536 |