问题2172--GJJ的日常之购物

2172: GJJ的日常之购物

时间限制: 3 Sec  内存限制: 128 MB
提交: 21  解决: 18
[状态] [讨论版] [提交] [命题人:]
题目描述
一天，GJJ去购物，来到商场门口，GJJ计划要买n个商品，第i个商品的坐标为（xi，yi），重量是wi。
GJJ比较任性，想按照商品编号从小到大的顺序将所有的商品的搬到车里（车在（0，0）的位置）；
GJJ可以几个商品一起搬，但在任何时候GJJ手中的商品重量不能超过最大载重C。
商场的过道只有横着的和竖着的。求GJJ行走的最短距离（GJJ的起始位置为（0，0））。

输入
第一行输入一个T(T<=10)，表示T组数据。
每组数据第一行为最大载重C（1<=C<=100），商品个数n(n<=100000);
接下来n行，每行为xi，yi，wi，(0<=xi,yi<=100,wi<=C)既商品的坐标和重量

输出
对于每组数据，输出总路径的最短长度。

样例输入 Copy 
2
10 4
1 2 3
1 0 3
3 1 4
3 1 4
5 1
1 1 2
样例输出 Copy 
14
4
来源/分类
 
[提交] [状态]