2 shunfurh 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
caozhy   Ds   Rxr 2017.01.02 20:46
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
POJ 3635 Full Tank? 最短路DP
给出一个图(1≤n≤1000,0≤m≤100001\leq n\leq 1000,0\leq m\leq 10000),每个点有加油站费用cic_i,对于每个询问,油箱容积cc的车从ss到ee的最小费用。如果这个图是个DAG的话很显然我们可以直接使用动态规划求解。 但它现在不是DAG,回忆起有篇论文是讲SPFA的应用的,不过没负边,用Dij+Heap即可求有环的动态规划。#include <cst
POJ3635 Full Tank?(最短路+DP)
n个城市之间有m条双向路。每条路要耗费一定的油量。每个城市的油价是固定并且已经给出的。有q个询问,表示从城市s走到e,油箱的容量为c,求最便宜的方案。 dp(i,j)表示走到城市i,剩余油量为j的最小花费。然后用优先队列更新,优先更新花费小的状态。走到一座城市,要么加油,要么走向下一个城市(在油量充足的情况下)。#include<cstdio> #include<cstring> #include
POJ 3635 Full Tank? 最短路变形
题意:给出一张图,n 网上大部分的思路都是类似于dij的那种扩展。 首先定义一个二维数组dp。 dp[i][j] 表示走到i点剩余j个单位的汽油时的最小花费 然后维护一个优先队列。  每次有两种可扩展的状态,一是加一个单位的油,二是走向邻接点,然后不断的将状态加入优先队列中 #include #include #include #include #include #d
poj3635—Full Tank?(spfa+dp)
题目大意:一辆车从起点到终点,给定汽车的邮箱容量,给出每个点加每单位油的价格,点与点间的距离,(起点油量为0)计算所需最少的费用。 解题思路:spfa+dp,dp[i][j]记录汽车到达第i个点所剩j单位油所用的费用,维护一个优先队列,将产生的新的状态压入队列,前一个状态向下产生的两个新的状态1.汽车在原结点加一个单位的油2.汽车驶向下一个结点。 #include #in
POJ 3635 Full Tank?(BFS)
题目链接:Click here~~ 题意: n 个点的无向图,边权值为距离,点权值为油价。你开着一辆油箱容量为 c 的坦克,从 s 到 e。问最少花费多少钱。 解题思路: 很容易想到状态, dp[i][j] 表示 到达 i 点剩余油量为 j 的时候的最小花费。 转移好转,但是不好找到最优状态,所以要用节点存储状态,然后用优先队列,每次弹出的节点(cost 最小)一
HDU 1676 Full Tank? 限制最短路(difficult)
点击打开链接 Full Tank? Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 155    Accepted Submission(s): 71 Problem Description After
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?)
我感觉是dp类型的吧。。。。 discuss里一个讲解把状态的设置说的很好 设一个 money[1001][101] 表示 到点i时, 油量为j 的最小花费; 然后用dijstra的广搜变种来搜即可: 每次找一个最小花费点, if money[x][y + 1]满足, 拓