8582: DPL_2_B : Chinese Postman Problem
[Creator : ]
Description
For a given weighted undirected graph G(V,E), find the distance of the shortest route that meets the following criteria:
- It is a closed cycle where it ends at the same point it starts.
- The route must go through every edge at least once.
Input
The first line consists of the integers $|V|$ is the number of vertices and $|E|$ is the number of edges in the graph. The graph vertices are named with the numbers $0, 1,..., |V|-1$ respectively.
In the following $|E|$ lines, $s_i$ and $t_i$ represent source and target vertices of $i$-th edge (directed) and $d_i$ represents the distance between $s_i$ and $t_i$ (the $i$-th edge).
Output
Print the shortest distance in a line.
Constraints
$2 ≤ |V| ≤ 15$
$0 ≤ |E| ≤ 1,000$
$0 ≤ d_i ≤ 1,000$
$s_i ≠ t_i$
The graph is connected
$0 ≤ |E| ≤ 1,000$
$0 ≤ d_i ≤ 1,000$
$s_i ≠ t_i$
The graph is connected
Sample 1 Input
4 4
0 1 1
0 2 2
1 3 3
2 3 4
Sample 1 Output
10
Sample 2 Input
4 5
0 1 1
0 2 2
1 3 3
2 3 4
1 2 5
Sample 2 Output
18
Sample 3 Input
2 3
0 1 1
0 1 2
0 1 3
Sample 3 Output
7
HINT
相同题目：DPL_2_B。