#P3602. 十万人的地铁
十万人的地铁
十万人的地铁
题目描述
陆仁甲和陆仁乙去搭地铁。陆仁甲要从循礼门去广埠屯,陆仁乙要从广埠屯去循礼门。两人都很清楚武汉地铁的收费规则。
武汉地铁 2 号线是一条直线,共有 个地铁站,依次编号为 。搭乘地铁需使用武汉通。乘客进站和出站时各刷一次卡,进站时在卡上记录起始站,出站时按卡上记录的起始站和实际出站站之间的距离扣费。设从第 站进站、第 站出站的代价为 ,则
计费与乘车时间无关。在第 站进站,哪怕在地铁上待一整天,从第 站出站仍只需付 。
两人想到一个免费乘车方案。陆仁甲从循礼门、陆仁乙从广埠屯进站,分别坐到途中的螃蟹岬站下车,在站内交换武汉通。随后陆仁甲继续坐到广埠屯,他手上的卡记录的起始站恰好是广埠屯,因此扣费 元。同理陆仁乙坐到循礼门后也扣费 元。
现在有 个人搭地铁,分别编号为 。第 个人从第 站出发去第 站,,并沿最短路线乘车。
- 若 ,他的路线依次经过 。
- 若 ,他的路线依次经过 。
开始时,所有人都已在自己的起始站刷卡进站,第 个人位于第 站。每次可以执行以下两种操作之一。
- 操作
0 x y让编号为 的乘客乘车到第 站后下车。第 站必须位于该乘客当前位置至目的站 的路线中,且不能等于他的当前位置。,。 - 操作
1 x y让编号为 和 的乘客交换武汉通。两个人此时必须在同一个站。。
一次操作中未提及的人在原地等候。所有操作结束后,第 个人必须在第 站,所有人一起刷卡出站。求使所有人的扣费总和最小的乘车方案。
输入格式
第一行一个正整数 ,表示数据组数。每组数据如下。
- 第一行两个用空格隔开的正整数 ,分别表示人数和地铁站数。
- 接下来 行,每行两个用空格隔开的正整数 ,分别表示第 个人的起始站和终点站。,。
输出格式
对每组数据输出一个最优方案。若有多个方案的扣费总和都最小,输出任意一个即可。
每组第一行输出两个用空格隔开的非负整数 ,分别表示最小总扣费和操作数。要求 。
接下来 行,每行输出三个整数 type x y,分别表示操作类型和两个参数。类型为 或 , 的限制如题目描述。
样例
2
3 7
1 7
1 6
5 1
2 7
1 7
7 1
7 5
0 1 5
1 3 1
0 1 7
0 2 6
0 3 1
0 3
0 1 7
1 2 1
0 2 1
数据范围与约定
对于所有数据,。
| 测试点 | ||
|---|---|---|
| 1 | ||
| 2 | ||
| 3 | ||
| 4 | ||
| 5 | ||
| 6 | ||
| 7 | ||
| 8 | ||
| 9 | ||
| 10 |
原作者 VFleaKing 注明这是虚构题设。作者当时实测进站后从原站出站会扣费 元,请勿模仿题中做法。