题解

题面描述

外卖骑手需要在给定的起始地点 $S_n$ 和总工作时间 $t$ 内，依次选择若干订单进行配送。每个订单由出发站点 $s$、到达站点 $d$ 和配送费 $p$ 三元组表示，且 $s \ne d$。若同一对 $(s,d)$ 存在多笔订单，可将它们合并，合并后耗时仍为 $1$ 单位，但收入为这批订单费用之和。每次配送无论合并与否，均耗时 $1$，且每笔订单只能配送一次。配送结束条件为工作时间用尽或当前地点无可接订单。输出骑手可获得的最大总收入及对应路径，若多条路径收入相同，则取字典序最小的路径。

思路

1. 合并订单权重
   使用哈希表将每个相同起点 $s$、终点 $d$ 的订单费用相加，得到边权值 $w_{s,d}$。

题目内容

外卖骑手是一个和时间赛跑的工作。由于外卖订单一般集中在一日三餐的时间，具有时间短突发量大的特点，骑手们需要在订单集中的时间段内尽可能送出更多的订单以获得更多的收入。

骑手的工作流程大致是这样的，从一个商家出发，选择一个订单，送到目的地点，在目的地点接新的订单送到下一个目的地，如此循环。一个订单只能配送一次，骑手不能重复配送相同的订单。

从出发地点到取的地点的一次配送需要消耗1单位的时间。同一个地点可能发出多笔订单，其中一些订单可能要送往同一个目的地，这些起点和终点相同的订单可以合并配送，合并配送的多笔订单和单笔订单一样都只消耗1单位的时间。

简化起见，我们不区分商家和配送目的地点，统一视作地图上的一个地点。骑手的工作时间总时间是给定的，如果剩余的工作时间为0，则配送工作结束;如果到达目的地点之后，没有再从该地点发出的订单，则配送工作结束。

假设地图上有$N$个地点，每个地点有$[0,X]$个待送出的订单，每个订单以$[s,d,f]$来表示，一共有$M$个订单。其中$s$是出发站点编号，$d$是目的站点编号，$p$是这笔订单的配送费，约定$s\ !=d$。给定骑手的出发地点编号$S_n$和工作总时间$t$，请计算出骑手最多能获得的收入。

具体每个取值的范围说明:

输入描述

第1行为空格分隔的$2$个整数，分别表示骑手的出发地点编号$S_n$和工作总时间$t$；

第$2$行为一个表示订单数量的整数$M$;

第$3$行开始的$M$行每行都是以空格分隔的$3$个整数$s,d$和$p,s$表示出发站点，$d$表示目标站点，$p$表示订单收入。

输出描述

第$1$行是一个整数，表示骑手能获得的最多的收入;

第$2$行是空格分隔的整数数组，每个数字是一个地点编号，表示从开始到结束的配送路径。当多个路径能够获取相同的收入时，输出从前往后数字序最小的路径。

样例1

输入

0 2
6
0 1 2
0 5 3
5 3 3
1 2 3
2 4 10
1 3 4

输出

6
0 1 3

说明

如图所示：

工作时间$t$为$2$的条件下，从$0$出发，节点$4$不可达，可选的线路是:

$1，0->1->3$收入是$2+4=6$

$2，0->5->3$收入是$3+3=6$

$2，0->1->2$收入是$2+3=5$

线路$1$和线路$2$的收入最大，都是$6$，选择数字序最小的路径$0->1->3$,输出总收入$6$和线路$0\ 1\ 3$

样例2

输入

3 2
5 
3 4 10
4 5 5
4 5 10
4 5 15
5 6 20

输出

40
3 4 5

说明

如图所示：

工作时间$t$为$2$的条件下，可以进行$2$次配送，其中从$3$到$4$消耗$1$的时间，可以获取收入$10$。从$4$到$5$有$3$个订单，这$3$个订单的起终点相同(都是从$4$到$5$)，可以合并配送，收入$5+10+15=30$，只消耗$1$的时间。

所以唯一的路线是$3->4->5$，总收入为$10+30=40$

样例3

输入

1 2
5 
1 2 5
2 3 10
2 3 8
2 4 6
4 5 6

输出

23
1 2 3

说明

如图所示：

工作时间$t$为$2$的条件下，从$1$出发，可选的线路是: $1，1->2->3$ 注意从$1$到$3$有$2$个要配送的外卖，可以合并配送，时间只算$1$，所以总收入是$5+8+10=23$

$2，1->2->4$收入是$5+6=11$

线路$1$的收入最大，选择线路$1$，输出总收入$23$和线路$0\ 1\ 3$