加满油箱问题

一 问题描述

城市之间的油价是不一样的，编写程序，寻找最便宜的城市间的旅行方式。在旅行途中可以加满油箱。假设汽车每单位距离使用一单位燃料，从一个空油箱开始。

二 输入和输出

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 升油；如果依靠加的油能够走到下一个节点，就走到下一个节点（减去路上消耗的油，花费不变）；在广度优先搜索中将所有可扩展的节点都加入优先队列中，如果达到终点，则返回花费。

五 算法设计

六 代码

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 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_;
    }
 
    @Override
    public int compareTo(Object o) {
        return this.cost - ((node) o).cost;
    }
}

七测试