题意：
n个城市之间有m条双向路。每条路要耗费一定的油量。每个城市的油价是固定并且已经给出的。有q个询问，表示从城市s走到e，油箱的容量为c，求最便宜的方案。
思路：
用Dijkstra+Heap即可求有环的动态规划.
代码：
#include <cstdio> #include <cstring> #include <queue> using namespace std; const int N = 1001, M = 20001, inf = 0x7f7f7f7f; int h[N], p[M], v[M], w[M], c[N], cnt = 0; int dp[N][101], vis[N][101], s, t, cap; struct Data { int x, o, c; }; bool operator <(Data a, Data b) { return a.c>b.c; } void add(int x, int y, int z) { p[++cnt] = h[x]; w[cnt] = z; v[cnt] = y; h[x] = cnt; } int dij() { priority_queue<Data> q; memset(dp, 127, sizeof dp); memset(vis, 0, sizeof vis); dp[s][0] = 0; q.push((Data) { s, 0 }); while (!q.empty()) { Data u = q.top(); q.pop(); vis[u.x][u.o] = 1; if (u.x == t) return u.c; if (u.o < cap && !vis[u.x][u.o + 1] && dp[u.x][u.o + 1] > dp[u.x][u.o] + c[u.x]) { dp[u.x][u.o + 1] = dp[u.x][u.o] + c[u.x]; q.push((Data) {u.x, u.o + 1, dp[u.x][u.o + 1]}); } for (int i = h[u.x]; i; i = p[i]) if (u.o >= w[i] && !vis[v[i]][u.o - w[i]] && dp[v[i]][u.o - w[i]] > dp[u.x][u.o]) { dp[v[i]][u.o - w[i]] = dp[u.x][u.o]; q.push((Data) {v[i], u.o - w[i], dp[v[i]][u.o - w[i]]}); } } return -1; } int main() { int n, i, m, q; scanf("%d%d", &n, &m); for(i=0;i<n;i++) scanf("%d", c + i); while (m--) { scanf("%d%d%d", &s, &t, &cap); add(s, t, cap); add(t, s, cap); } scanf("%d", &q); while (q--) { scanf("%d%d%d", &cap, &s, &t); int re = dij(); if (re == -1) puts("impossible"); else printf("%d ", re); } return 0; }