shunfurh 于 2017.01.01 22:36 提问

Full Tank?

Description

After going through the receipts from your car trip through Europe this summer, you realised that the gas prices varied between the cities you visited. Maybe you could have saved some money if you were a bit more clever about where you filled your fuel?

To help other tourists (and save money yourself next time), you want to write a program for finding the cheapest way to travel between cities, filling your tank on the way. We assume that all cars use one unit of fuel per unit of distance, and start with an empty gas tank.

Input

The first line of input gives 1 ≤ n ≤ 1000 and 0 ≤ m ≤ 10000, the number of cities and roads. Then follows a line with n integers 1 ≤ pi ≤ 100, where pi is the fuel price in the ith city. Then follow m lines with three integers 0 ≤ u, v < n and 1 ≤ d ≤ 100, telling that there is a road between u and v with length d. Then comes a line with the number 1 ≤ q ≤ 100, giving the number of queries, and q lines with three integers 1 ≤ c ≤ 100, s and e, where c is the fuel capacity of the vehicle, s is the starting city, and e is the goal.

Output

For each query, output the price of the cheapest trip from s to e using a car with the given capacity, or "impossible" if there is no way of getting from s to e with the given car.

Sample Input

5 5
10 10 20 12 13
0 1 9
0 2 8
1 2 1
1 3 11
2 3 7
2
10 0 3
20 1 4
Sample Output

170
impossible

1个回答

caozhy      2017.01.02 20:46

POJ 3635 Full Tank? 最短路DP

POJ3635 Full Tank?(最短路+DP)
n个城市之间有m条双向路。每条路要耗费一定的油量。每个城市的油价是固定并且已经给出的。有q个询问，表示从城市s走到e，油箱的容量为c，求最便宜的方案。 dp(i,j)表示走到城市i，剩余油量为j的最小花费。然后用优先队列更新，优先更新花费小的状态。走到一座城市，要么加油，要么走向下一个城市(在油量充足的情况下)。#include<cstdio> #include<cstring> #include
POJ 3635 Full Tank? 最短路变形

poj3635—Full Tank？（spfa+dp）

POJ 3635 Full Tank?（BFS）

HDU 1676 Full Tank? 限制最短路（difficult）

CSUOJ 1891 Full Tank? 有约束条件下的最短路 分支限界法？
Description After going through the receipts from your car trip through Europe this summer, you realised that the gas prices varied between the cities you visited. Maybe you could have saved some mon
UVA 11367 - Full Tank? dijkstra+DP
n个城市有m条道路。每个城市的油价不一样，给出起点s和终点t，以及汽车的油箱的容量，求从城市s到城市 t 的最便宜路径。（一开始油箱是空的，你每次可以选择加多少升。假设每单位的距离消耗1L汽油）
Poj3635 Full Tank?
/* 从一个城市走到另一个城市，每个城市都有加油站，但是价格不同，油箱大小固定，计算行走过程中的最小花费。 1。使用优先队列，标记，链表表示边，二维数组超时 2。每次从优先队列中取的最小值，执行 油箱加一操作，if(v + 1 m + Price[c]|| Money[c][
poj 3635（full tank？）