4458 . 探險之路

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

餘切
$\Huge\text{freeh1}$

User's AC Ratio

100.0% (8/8)

Submission's AC Ratio

50.8% (33/65)

Tags

Mid MST

Description

小龍在家裡宅了許久之後，終於決定出去走走了!

他來到了一個秘境，總共有$n$個景點可以去探訪，而景點間總共有$m$條路徑可以走，每一條路經過都需要花費$k$元，花費過一次之後，重覆再走這條路就不用花錢了。小龍很想要每一個景點都看過一次，可是最近買太多遊戲所以快要沒錢了!所以他希望能夠在最少花費的情況下探訪所有的景點，你可以幫他處理這個問題嗎?

Input Format

第一行輸入兩個正整數$n(2 \leq n \leq 4000),m(n-1 \leq m \leq \frac {n(n-1)}{2})$代表景點數和路徑數量。

接下來$m$行每行有$a,b,k(1 \leq k \leq 2147483647)$ 代表從$a$景點到$b$景點需要花費$k$元。

Output Format

請輸出經過所有景點的最小花費。

Sample Input 1

3 3
1 2 3
1 3 2
2 3 1

Sample Output 1

3

Hints

可能會需要在程式前面加ios_base::sync_with_stdio(false);cin.tie(0) 才會過喔!

Problem Source

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Memory Limit (RSS, KiB) Output Limit (KiB) Subtasks
0 3000 250000 250000 65536
1 3000 250000 250000 65536
2 3000 250000 250000 65536
3 3000 250000 250000 65536
4 3000 250000 250000 65536
Submit
Back to Top