登录
  • #刷题

汽车加油问题

mgccl
1203
0
给一个图G=(V,E).

一辆车, 起始的时候有a升油. 油箱能装b升油. 车能通过一条边, 如果边的油耗比车的油箱里的油少. 两个不同的问题:

1. 如果有些顶点是加油站, 每次到达这些顶点就会加满油. 找到耗油最少的s到t的路径. (是耗油, 不是加的油).

2. 所有的顶点都是加油站, 每个加油站会有不用的油价, 找到用钱最少的s到t的路径. 在加油站并不需要一次性加满油.
0条回复
热度排序

发表回复