58 . 城鎮賽車比賽

Submit
Status
Ranklist
Back to Problems List

User's AC Ratio

100.0% (10/10)

Submission's AC Ratio

81.0% (17/21)

Tags

2020 高階競技程式設計 - Contest #5

Description

你是賽車比賽的負責人員，已經確定下次比賽將在某個城鎮舉辦比賽；標準的比賽路線為起點與終點相同，每個路段在比賽路線中只能被使用一次，且只有一個方向能用，而這個比賽路線當天才會公布。

城鎮路線錯綜複雜，每條路段與路段之間的交接處以 $1, \cdots, n$ 編號，且其中共有 $m$ 條路。
為了防止選手們賽前在城鎮中進行非法訓練，城鎮中每個路段都能架設監視器以捕捉犯規者。

但不同路段有不同的架設成本，且由於經費要盡量節省，所以要以最低的成本架設監視器。

Input Format

第一列有 $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)$。

輸入保證城鎮是個連通圖，畢竟當代(?)賽車比賽得是連通的。

Output Format

輸出裝設監視器的最低總成本。

Sample Input 1

6 7
1 2 6
1 4 7
2 3 3
6 3 3
5 2 3
4 5 4
5 6 4

Sample Output 1

6

Hints

第一筆範例以圖例表示為

點上數字為交接處編號，邊上數字為裝設監視器的成本
而最低成本 $6 = 3 + 3$ 為在路段 $(2, 3), (2, 5)$ 裝設監視器
在這兩處裝攝影機，這樣不管在何處出發然後回到起點，都能被監視器捕捉到

Problem Source

UVa Online Judge 1234 RACING

Subtasks

No. Testdata Range Score
1 0~119 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 50 65536 65536 1
1 50 65536 65536 1
2 50 65536 65536 1
3 50 65536 65536 1
4 50 65536 65536 1
5 50 65536 65536 1
6 50 65536 65536 1
7 50 65536 65536 1
8 50 65536 65536 1
9 50 65536 65536 1
10 50 65536 65536 1
11 50 65536 65536 1
12 50 65536 65536 1
13 50 65536 65536 1
14 50 65536 65536 1
15 50 65536 65536 1
16 50 65536 65536 1
17 50 65536 65536 1
18 50 65536 65536 1
19 50 65536 65536 1
20 50 65536 65536 1
21 50 65536 65536 1
22 50 65536 65536 1
23 50 65536 65536 1
24 50 65536 65536 1
25 50 65536 65536 1
26 50 65536 65536 1
27 50 65536 65536 1
28 50 65536 65536 1
29 50 65536 65536 1
30 50 65536 65536 1
31 50 65536 65536 1
32 50 65536 65536 1
33 50 65536 65536 1
34 50 65536 65536 1
35 50 65536 65536 1
36 50 65536 65536 1
37 50 65536 65536 1
38 50 65536 65536 1
39 50 65536 65536 1
40 50 65536 65536 1
41 50 65536 65536 1
42 50 65536 65536 1
43 50 65536 65536 1
44 50 65536 65536 1
45 50 65536 65536 1
46 50 65536 65536 1
47 50 65536 65536 1
48 50 65536 65536 1
49 50 65536 65536 1
50 50 65536 65536 1
51 50 65536 65536 1
52 50 65536 65536 1
53 50 65536 65536 1
54 50 65536 65536 1
55 50 65536 65536 1
56 50 65536 65536 1
57 50 65536 65536 1
58 50 65536 65536 1
59 50 65536 65536 1
60 50 65536 65536 1
61 50 65536 65536 1
62 50 65536 65536 1
63 50 65536 65536 1
64 50 65536 65536 1
65 50 65536 65536 1
66 50 65536 65536 1
67 50 65536 65536 1
68 50 65536 65536 1
69 50 65536 65536 1
70 50 65536 65536 1
71 50 65536 65536 1
72 50 65536 65536 1
73 50 65536 65536 1
74 50 65536 65536 1
75 50 65536 65536 1
76 50 65536 65536 1
77 50 65536 65536 1
78 50 65536 65536 1
79 50 65536 65536 1
80 50 65536 65536 1
81 50 65536 65536 1
82 50 65536 65536 1
83 50 65536 65536 1
84 50 65536 65536 1
85 50 65536 65536 1
86 50 65536 65536 1
87 50 65536 65536 1
88 50 65536 65536 1
89 50 65536 65536 1
90 50 65536 65536 1
91 50 65536 65536 1
92 50 65536 65536 1
93 50 65536 65536 1
94 50 65536 65536 1
95 50 65536 65536 1
96 50 65536 65536 1
97 50 65536 65536 1
98 50 65536 65536 1
99 50 65536 65536 1
100 500 65536 65536 1
101 500 65536 65536 1
102 500 65536 65536 1
103 500 65536 65536 1
104 500 65536 65536 1
105 500 65536 65536 1
106 500 65536 65536 1
107 500 65536 65536 1
108 500 65536 65536 1
109 500 65536 65536 1
110 500 65536 65536 1
111 500 65536 65536 1
112 500 65536 65536 1
113 500 65536 65536 1
114 500 65536 65536 1
115 500 65536 65536 1
116 500 65536 65536 1
117 500 65536 65536 1
118 500 65536 65536 1
119 500 65536 65536 1
Submit
Status
Ranklist
Back to Top