acm 图论吃豆豆 Time Limit:1000 MS Memory Limit:32768 K Total Submit:25 (16 users) Total Accepted:15 (15 users) Special Judge:No Description 一天Woods和他的GrilFriend（GF）来到了一个童话王国的小镇里,镇上有许多豆豆（如

acm 图论吃豆豆 Time Limit:1000 MS Memory Limit:32768 K Total Submit:25 (16 users) Total Accepted:15 (15 users) Special Judge:No Description 一天Woods和他的GrilFriend（GF）来到了一个童话王国的小镇里,镇上有许多豆豆（如
acm 图论
吃豆豆
Time Limit:1000 MS
Memory Limit:32768 K
Total Submit:25 (16 users)
Total Accepted:15 (15 users)
Special Judge:No
Description
一天Woods和他的GrilFriend（GF）来到了一个童话王国的小镇里,镇上有许多豆豆（如下图中的每个圆形为一个豆豆）,每个豆豆有通向东,南,西,北,东南,东北,西北,西南八个方向的道路.其中直线道路的距离为1米,斜线道路的距离为根号2米.GF一看见吃的就饿了……你能算出吃且只吃所有豆豆一次,最后回到起点的最短路程吗?
如图所示为一个2
x 3的图,最短距离（如红线所示）为6米.
Input
多组测试数据.每组测试数据一行,包括两个整数N,M（1 < m < 50 and 1 < n <
50.）,代表图的大小为N行M列.
Output
对于每组数据输出一行,输出吃且只吃所有豆豆一次,最后回到起点的最短路程.（精确到两位小数）.
Sample Input
2 2
2 3
Sample Output
4.00
6.00
Hint

acm 图论吃豆豆 Time Limit:1000 MS Memory Limit:32768 K Total Submit:25 (16 users) Total Accepted:15 (15 users) Special Judge:No Description 一天Woods和他的GrilFriend（GF）来到了一个童话王国的小镇里,镇上有许多豆豆（如
最小生成树题目POJ：1251 1258 2395 2485 2560
最短路径POJ：1797(易） 1062（难）1125（难)
我也是在hdoj上做题的 不过练习图论的时候在poj上做的
hdu1102,1233 这俩是hdu的,后来随便做题的时候碰到的
希望对你能有所帮助.