27. 阿源的田地 5

0 Judge

Code: 0


阿源的田地 5

題目敘述

為了要增加銷量,所以阿源決定要去挨家挨戶拜訪推銷他的農產品,為了簡化問題,我們將每個家視為一個點,每條道路連接兩個家且長度為$len(1 \leq len \leq 10^6)$公里,每條路都是雙向的,任兩個家間最多只有一條路,現在請幫阿源找出拜訪完所有的家最短需要多少公里的路,保證這張圖連通。

輸入說明

輸入的第一行包含一個正整數 $T(T\leq 10)$,代表接下來有 $T$ 個測試資料。 每筆測試資料第一行會有兩個正整數 $n(\lt 19)$ , $m(\leq n*(n-1)/2)$,代表有$n$個家需要拜訪,總共有$m$條路,任兩家中間最多只會有一條路。 接下來會有m行,每行會有$u,v,len$,三個正整數($u \neq v$),代表有一條長度為$len$的道路連接$u$跟$v$兩個住家。

輸出說明

對於每個測試資料輸出一個正整數代表最短經過所有住家所需走過的公里數。

範例輸入

範例輸出

範例解釋

最短的走訪順序其中一個為 6->3->1->2->1->3->5->3->4

子題一[10%]

$n \leq 10$

子題二[40%]

$n \lt 19, len = 1$

子題三[50%]

無其他限制


Judge Setting

run-time limit: 10000 ms
memory limit: 104857600 byte
測資數量: 3