## Public Bike Management

There is a public bike service in Hangzhou City which provides great convenience to the tourists from all over the world. One may rent a bike at any station and return it to any other stations in the city.

The Public Bike Management Center (PBMC) keeps monitoring the real-time capacity of all the stations. A station is said to be in perfect condition if it is exactly half-full. If a station is full or empty, PBMC will collect or send bikes to adjust the condition of that station to perfect. And more, all the stations on the way will be adjusted as well.

When a problem station is reported, PBMC will always choose the shortest path to reach that station. If there are more than one shortest path, the one that requires the least number of bikes sent from PBMC will be chosen.

The above figure illustrates an example. The stations are represented by vertices and the roads correspond to the edges. The number on an edge is the time taken to reach one end station from another. The number written inside a vertex $S$ is the current number of bikes stored at $S$. Given that the maximum capacity of each station is 10. To solve the problem at $S_3$, we have 2 different shortest paths:

1. PBMC -> $S_1$ -> $S_3$. In this case, 4 bikes must be sent from PBMC, because we can collect 1 bike from $S_1$ and then take 5 bikes to $S_3$, so that both stations will be in perfect conditions.
2. PBMC -> $S_2$ -> $S_3$. This path requires the same time as path 1, but only 3 bikes sent from PBMC and hence is the one that will be chosen.

### Input Specification:

Each input file contains one test case. For each case, the first line contains 4 numbers: $C_{max} (≤100)$, always an even number, is the maximum capacity of each station; $N (≤500)$, the total number of stations; $S_p$, the index of the problem station (the stations are numbered from 1 to $N$, and PBMC is represented by the vertex 0); and $M$, the number of roads. The second line contains $N$ non-negative numbers $C_i (i=1,⋯,N)$ where each $C_i$ is the current number of bikes at $S_i$ respectively. Then $M$ lines follow, each contains 3 numbers: $S_i$, $S_j$, and $T_{ij}$ which describe the time $T_{ij}$ taken to move between stations $S_i$ and $S_j$. All the numbers in a line are separated by a space.

### Output Specification:

For each test case, print your results in one line. First output the number of bikes that PBMC must send. Then after one space, output the path in the format: 0−>$S_1$−>⋯−>$S_p$. Finally after another space, output the number of bikes that we must take back to PBMC after the condition of $S_p$ is adjusted to perfect.

Note that if such a path is not unique, output the one that requires minimum number of bikes that we must take back to PBMC. The judge’s data guarantee that such a path is unique.

## 思路

• 你在去问题车站的路上要把所有车站都调整到最佳状态，少了补充，多的带回
• 不可以再回来路上调整
• 路是双向的
• 两个路线的比较维度其实有三个
1. 花费时间
2. 带过去的车数量
3. 带回的车的数量
• 不可以只用Dijkstra，因为这一个车站的最优点不一定是下一个车站的最优点，例如在在这个车站的有两条路线，他们里程相等，一个需要带3辆拿回3辆，一个需要带4辆拿回5辆，这时候Dijkstra会选择一个路线。如果下个车站就是终点，它缺5辆车，选第一个路线就是带5辆拿回0辆，选第二个路线就是带4辆不用拿回。这样子就是第二种路线最优了。Dijkstra 仅仅考虑目前的最优状态
• 所以只能使用DFS。很多博主的答案是先Dijkstra算最短路线，再DFS求带走和带回的车，我认为这多此一举了，直接DFS就可以了
• 关于自行车数量和带回带走，有一些小技巧可以简化分析。方法是这样
• 给每个站点已有的自行车数量标记为已有数量 - 完美状态下的数量
• 这样，是正的就需要带走，是负的就需要给他带来
• 遍历的时候，用目前的take带走总数加上修改过的站点自行车数
• 如果修改过的自行车数是负的，那么就需要以前的take来填补，所以加上没毛病
• 如果修改过的自行车数是正的，那么需要加上的更多
• 如果目前的take加上后变成了负数，说明以前的不够填补，那么需要send += take，即要多带车了，同时把take置0

## 代码

### Python3

#### 数据结构

• stations[]是保存所有车站的列表，一个车站也是一个列表
• station 的第一个参数表示从0点到这个车站的最短距离
• station 的第二个参数表示这个站点的车子数量
• station 的第三个参数表示这个站点的所有路线，是一个列表。
• 一个路线是一个元祖，
• 第一项为目的地，
• 第二项为时间。
• station 的第四个参数表示这个站点有没有被访问过
• best是目前已有最佳情况，temp是目前计算中的情况
• 对于best列表和temp列表，第一项是时间，第二项是send，第三项是take，第四项是path

#### 算法

• 如果到了终点，比较需不需要更新目前最佳的best。
• 如果不到终点，记录好现在的状态，遍历这个点的下一个点。
• 这个点结束了要回溯。