问题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
来源/分类