题意：一辆汽车在一张无向图中开告诉你每个城市加油的费用。每次给q个查询（起点，终点，油箱容量）问你最小花费是多少。
思路：一道Dijkstra状态的题目。在这种最短路问题中一维的dis数组记录的信息往往不能很好的解决问题，所以我们要给dis数组增加维数来使每个状态唯一。这其实就是结合了动态规划的思想，然后我们在考虑每个状态能怎么转移（这其实就是单个结点从队列中弹出来的处理过程）这样一道题就做出来了。
对于这道题，我们增加一维表示当前汽车的剩油量，然后每个状态有两种转移方式1.直接开去下一个节点2.加一格油。最后统计一下目标节点所有油量的花费最小值，就能得出答案了。
代码如下：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cmath> 5 #include <cstring> 6 #include <algorithm> 7 #include <queue> 8 #include <stack> 9 #include <vector> 10 #define MP(a, b) make_pair(a, b) 11 #define PB(a) push_back(a) 12 13 using namespace std; 14 15 typedef long long ll; 16 typedef struct {int p, o;}S; 17 typedef pair<int, S> pis; 18 typedef pair<int, int> pii; 19 typedef pair<unsigned int, unsigned int> puu; 20 typedef pair<int ,double> pid; 21 typedef pair<ll, int> pli; 22 23 const int INF = 0x3f3f3f3f; 24 const double eps = 1e-6; 25 const int LEN = 1010; 26 vector<pii> Map[LEN]; 27 int n, m, oil[LEN], dis[LEN][110], vis[LEN][110], minans; 28 struct cmp{ 29 bool operator() (pis a, pis b){return a.first > b.first;} 30 }; 31 32 inline S MS(int a, int b){S ret; ret.p = a, ret.o = b;return ret;} 33 34 void read(int &ret) 35 { 36 char c; 37 while((c = getchar())<‘0‘ || c>‘9‘); 38 ret = 0; 39 while(c>=‘0‘ && c<=‘9‘){ 40 ret = ret*10+(c-‘0‘); 41 c = getchar(); 42 } 43 } 44 45 void Dijkstra(int s, int e, int lv) 46 { 47 priority_queue<pis, vector<pis>, cmp> q; 48 memset(vis, 0, sizeof vis); 49 memset(dis, 0x3f, sizeof dis); 50 dis[s][0] = 0;minans = INF; 51 q.push(MP(dis[s][0], MS(s,0))); 52 while(!q.empty()){ 53 pis nvex = q.top(); q.pop(); 54 S ns = nvex.second; 55 int nv = ns.p, no = ns.o; 56 if(vis[nv][no])continue; 57 vis[nv][no] = 1; 58 59 if(no+1<=lv && dis[nv][no+1] > dis[nv][no] + oil[nv]){ 60 dis[nv][no+1] = dis[nv][no] + oil[nv]; 61 q.push(MP(dis[nv][no+1], MS(nv,no+1))); 62 } 63 for(int i=0; i<Map[nv].size(); i++){ 64 int x = Map[nv][i].first, y = Map[nv][i].second; 65 if(y <= no && dis[x][no-y] > dis[nv][no]){ 66 dis[x][no-y] = dis[nv][no]; 67 q.push(MP(dis[x][no-y], MS(x,no-y))); 68 } 69 } 70 } 71 } 72 73 int main() 74 { 75 // freopen("in.txt", "r", stdin); 76 77 int a, b, v, q, ans; 78 while(scanf("%d%d", &n, &m)!=EOF){ 79 for(int i=0; i<n; i++)Map[i].clear(); 80 for(int i=0; i<n; i++)read(oil[i]); 81 for(int i=0; i<m; i++){ 82 read(a);read(b);read(v); 83 Map[a].PB(MP(b, v)); 84 Map[b].PB(MP(a, v)); 85 } 86 read(q); 87 for(int i=0; i<q; i++){ 88 read(v);read(a);read(b); 89 Dijkstra(a, b, v); 90 ans = INF; 91 for(int i=0; i<=v; i++)ans = min(ans, dis[b][i]); 92 if(ans!=INF)printf("%d\n", ans); 93 else puts("impossible"); 94 } 95 } 96 return 0; 97 }