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 ewith 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
思考：其实这题很像B题B - ROADS。其中也是用了邻接表和BFS，只是思想有点不同而已，但是做法还是一样的……
思路：
涉及两个维的图最短路，一个是费用，一个是地点。（比如在位置0有1升油是一个点,在位置0有2升油又是另外一个点)
如果把这个点抽象出来，把费用看过边，那么最少费用就可以类似dijsktra算法那样不断的加入点。
于是得到一个扩展结点的策略:
1.每一次加w中最小的油或者一升油（因为题目的条件这些都是整数，所以可以类似离散化处理,一点一点加入油)
2.如果加的油足够走到下一个结点,那就走到下一个结点吧(记得减去路上消耗的油,还有花费不变)
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define M 1010
#define INF 1000001
using namespace std;
typedef long long ll;
int n,m,t,fue,st,end,Min=INF,head[M],vis[M][M/10],price[M];
struct edge
{
int u,v,w,next;
} e[M*20];
struct node
{
int u,fuel,cost;
bool operator < (const node a)const
{
return a.cost<cost;
}
} s1,s2;
void add(int u,int v,int w)
{
e[t].v=v; e[t].w=w;
e[t].next=head[u]; head[u]=t++;
}
int bfs()
{
mem(vis,0);
priority_queue<node>q; //优先队列每次都取cost最小的
int u,fuel,cost;
s1.u=st; s1.fuel=0; s1.cost=0;
q.push(s1);
while(!q.empty())
{
s2=q.top(); q.pop();
u=s2.u; fuel=s2.fuel; cost=s2.cost;
if(u==end) return cost;
vis[u][fuel]=1;
int tem=1;
if(fuel+Min<fue) tem=Min; //因为+1会耗很多时间如果取w中最小的可以优化点
if(fuel<fue&&!vis[u][fuel+tem])
{
s2.fuel++; s2.cost+=price[u]; //以u与fuel来做结点标记
q.push(s2);
}
for(int i=head[u]; i!=-1; i=e[i].next) //邻接表取u相同的而v不同的
{
if(!vis[e[i].v][fuel-e[i].w]&&fuel>=e[i].w)
{
s2.u=e[i].v; s2.fuel=fuel-e[i].w; s2.cost=cost; //如果燃料能够走别的路了
q.push(s2);
}
}
}
return -1;
}
int main()
{
int u,v,w,i,k,ans;
scanf("%d%d",&n,&m);
mem(head,-1);
for(i=0; i<n; i++)
sca(price[i]);
for(i=0; i<m; i++)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,w); add(v,u,w); //邻接表来做
Min=min(Min,w); //取最小的以优化
}
scanf("%d",&k);
while(k--)
{
scanf("%d%d%d",&fue,&st,&end);
ans=bfs();
if(ans==-1) puts("impossible");
else pri(ans);
}
return 0;
}