九度Online Judge

OJ新增积分机制,如有任何问题或者建议,请发帖到九度论坛OJ意见反馈版,祝大家一切顺利!
亲,九度OJ官方微博开通了,欢迎你来粉!微博地址:weibo.com/jobdu

 题目1430-九度Online Judge,用代码记录你的成长之路!

题目1430:Shortest Path

时间限制:2 秒

内存限制:64 兆

特殊判题:

提交:229

解决:43

题目描述:

        There is one Master In ACM_DIY called "白衣少年"(White) whose motto is "I can HOLD ANY FEMALE". Since White is really busy with HOLDING FEMALES, he has no idea of the work that is given by his boss(MALE, of course), so can you help him to solve such a simple and really easy problem: 

        Find a shortest path which can go through all the edges at least once in a undirected graph. 

        If you can solve this problem, White may give you some "tips"(You know better!)

输入:

        T cases (1<=T<=5)

        For each case, the first line has 2 integers n and m (1 ≤ n ≤ 20, 0 ≤ m ≤ 100000), n is the amount of vertices, and m is the amount of edges. Follow m lines contain u,v,w. (1<=u,v<=n; 1<=w<=100000).u,v are 2 endpoints of the edge while w is the length of the edge .

输出:

        For each case, print one line with the length of shortest path, if the path does not exist, print -1.

样例输入:
2
2 3
1 1 1
1 2 1
1 2 1
3 2
1 2 3
2 3 4
样例输出:
3
7
来源:
第四届ACM_DIY群程序设计竞赛