一问题描述
城市之间的油价是不一样的，编写程序，寻找最便宜的城市间的旅行方式。在旅行途中可以加满油箱。假设汽车每单位距离使用一单位燃料，从一个空油箱开始。
二输入和输出
1输入
输入的第 1行包含n和 m，表示城市和道路的数量。下一行包含n个整数pi，其中 pi表示第i个城市的燃油价格。接下来的m行，每行都包含 3个整数u，v 和 d，表示在u和v之间有一条路，长度为d。接下来一行是查询数q。再接下来是q行，每行都包含 3个整数c、s和e，其中c是车辆的邮箱容量，s是起点城市，e是终点城市。
2输出
对于每个查询，都输出给定容量的汽车从s到e的最便宜旅程的价格，如果无法从s到e，则输出 "impossible"。
三输入和输出样例
1输入样例
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
2输出样例
170
impossible
四分析
本问题为加油站加油问题。给定n个节点、m条边，每走 1单位的路径都会花费 1单位的油量，并且不同的加油站价格是不同的。现在有一些询问，每一个询问都包括起点和终点及邮箱的容量，求从起点到终点所需的最少花费。可以采用优先队列分支限界法搜索。
涉及两个维度的图的最短路径，一个是费用，一个是地点。可以把当前节点对应的油量成多个节点（例如在位置 0有 1升油是一个节点，在位置 0有 2升油是一个节点），把费用看作边：每次都加 1升油；如果依靠加的油能够走到下一个节点，就走到下一个节点（减去路上消耗的油，花费不变）；在广度优先搜索中将所有可扩展的节点都加入优先队列中，如果达到终点，则返回花费。
五算法设计
1定义一个优先队列，将起点及当前油量、花费作为一个节点(st,0,0)入队。 2如果队列不空，则对头(u,vol,cost)出队，并标记该节点油量已扩展，vis[u][vol]=1。 3如果u正好是目标ed，则返回花费cost。 4如果当前油量小于邮箱容量，且u的油量vol + 1未扩展，则将该节点(u,vol+1,cost+price[u])入队。 5检查u所有临界点v，如果当前油量大于或等于边权w，且v节点的油量vol -w未扩展，则将该节点 (v,vol-w,cost)入队。 6转向步骤 2。六代码
package com.platform.modules.alg.alglib.poj3635;import java.util.PriorityQueue;public class Poj3635 {public String output = "";private final int maxn = 1005;private final int maxm = 20005;edge edge[] = new edge[maxm];int head[] = new int[maxn];boolean vis[][] = new boolean[maxn][105];int n;int m;int V;int st;int ed;int cnt;int price[] = new int[maxn];public Poj3635() {for (int i = 0; i < edge.length; i++) {edge[i] = new edge();}}void add(int u, int v, int w) {edge[cnt].v = v;edge[cnt].w = w;edge[cnt].next = head[u];head[u] = cnt++;}int bfs() {for (int i = 0; i < maxn; i++) {for (int j = 0; j < 105; j++) {vis[i][j] = false;}}PriorityQueue<node> Q = new PriorityQueue<>(); // 优先队列Q.add(new node(st, 0, 0));while (!Q.isEmpty()) {node cur = Q.peek();Q.poll();int u = cur.u, vol = cur.vol, cost = cur.cost;vis[u][vol] = true;if (u == ed) return cost;if (vol < V && !vis[u][vol + 1])Q.add(new node(u, vol + 1, cost + price[u]));for (int i = head[u]; i != -1; i = edge[i].next) {int v = edge[i].v, w = edge[i].w;if (vol >= w && !vis[v][vol - w])Q.add(new node(v, vol - w, cost));}}return -1;}public String cal(String input) {String[] line = input.split("\n");String[] words = line[0].split(" ");n = Integer.parseInt(words[0]);m = Integer.parseInt(words[1]);String[] pricestr = line[1].split(" ");for (int i = 0; i < n; i++) {price[i] = Integer.parseInt(pricestr[i]);}int u, v, w;cnt = 0;for (int i = 0; i < head.length; i++) {head[i] = -1;}for (int i = 0; i < m; i++) {String[] edgs = line[2 + i].split(" ");u = Integer.parseInt(edgs[0]);v = Integer.parseInt(edgs[1]);w = Integer.parseInt(edgs[2]);add(u, v, w);add(v, u, w);}int q = Integer.parseInt(line[2 + m]);for (int i = 0; i < q; i++) {String[] querys = line[3 + m + i].split(" ");V = Integer.parseInt(querys[0]);st = Integer.parseInt(querys[1]);ed = Integer.parseInt(querys[2]);int ans = bfs();if (ans == -1) output += "impossible";else {output += String.valueOf(ans) + "\n";}}return output;}}class edge {int v;int w;int next;}class node implements Comparable {int u;int vol;int cost;node(int u_, int vol_, int cost_) {u = u_;vol = vol_;cost = cost_;}@Overridepublic int compareTo(Object o) {return this.cost - ((node) o).cost;}}
