CF21D Traveling Graph

• 14通过
• 46提交
• 题目来源
• 评测方式 RemoteJudge
• 标签
• 难度 提高+/省选-
• 时空限制 500ms / 64MB
• 提示：收藏到任务计划后，可在首页查看。

题意翻译

给定一个有n个顶点，m条边的带边权无向图，要求从顶点1开始经过每一条边至少一次最后回到起点1，要求走过的边权值总和最小。 注意：可能有重边和自环 输入:第一行n，m，之后m行每行一条无向边 输出:一个整数w，代表最小边权和，若无解则输出-1

Translated by 稀神探女

题目描述

You are given undirected weighted graph. Find the length of the shortest cycle which starts from the vertex 1 and passes throught all the edges at least once. Graph may contain multiply edges between a pair of vertices and loops (edges from the vertex to itself).

输入输出格式

输入格式：

The first line of the input contains two integers $n$ and $m$ ( $1<=n<=15,0<=m<=2000$ ), $n$ is the amount of vertices, and $m$ is the amount of edges. Following $m$ lines contain edges as a triples $x,y,w$ ( $1<=x,y<=n,1<=w<=10000$ ), $x,y$ are edge endpoints, and $w$ is the edge length.

输出格式：

Output minimal cycle length or -1 if it doesn't exists.

输入输出样例

输入样例#1： 复制
3 3
1 2 1
2 3 1
3 1 1

输出样例#1： 复制
3

输入样例#2： 复制
3 2
1 2 3
2 3 4

输出样例#2： 复制
14

提示
标程仅供做题后或实在无思路时参考。
请自觉、自律地使用该功能并请对自己的学习负责。
如果发现恶意抄袭标程，将按照I类违反进行处理。