一组人要担任在一个特定城市举办的比赛的评委,他们需要找到最便宜的租车方式使得每个人都到达目标城市。他们观察发现,如果几个人在旅途的某一段坐同一辆租的车,就可以减少总费用。你的任务就是找出这些人应该采取的路线使得租车的总费用最小。
我们假定:
1. 租一辆车的费用与它行驶的距离成正比,没有燃油、保险、乘客人数多于一个等产生的额外费用。
2. 所有车的费用与行驶距离的比例相同。
3. 一辆车可以容纳任意数量的乘客。
4. 任意一对城市之间最多只有一条道路直接相连,每条道路都是双向的且长度大于0。
5. 每个人的起始城市到目标城市都至少有一种路线。
6. 若多个人的路线中经过同一城市,则这些人从该城市到目标城市必乘同一辆车。
7. 一个人可以乘一辆车到某个城市,再乘另一辆车离开该城市。