算法竞赛进阶指南——POJ-3635.Full Tank?(优先队列BFS)

素颜马尾好姑娘i 2022-04-24 20:54 102阅读 0赞

# [poj-3635.Full Tank?][poj-3635.Full Tank] #

### 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 e with 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

### 题意 ###

有N(1<=N<=1000)个城市和M(1<=M<=10000)条道路，构成一张无向图。在每个城市里边都有一个加油站，不同加油站的价格不一样。通过一条道路的油耗就是该道路的边权。现在你需要回答不超过100个问题，在每个问题中，请计算出一架油箱容量为C(1<=N<=100)的车子，从起点S开到终点T至少要花多少油钱？

### 思路 ###

通过这道题，深深的感受到了程序的离散性。  
这道题找的不是最短路径，而是最少花费。这就要合理的加油了，当然如果只存在两个点A,B,那从城市A到城市B最少花费就是AB之间的路径长度与A加油站的油价之积了。也就是加多少油就看它们之间的路径长度了。  
但这么想还不够，那如果三个城市A,B,C,A->B->C,从A到C的最少花费。要还是那么去算可能最后得到的还不是最优解，比如在A加油站的油价比在B加油站的油价低，再假设A到B，B到C的路径长度小于油箱的容量，这样的话，在A加油站把油加到可以到城市C的量，这样的花费肯定要比那种做法得出的花费少。所以还要考虑到两地油价的高低，油箱容量是否可支撑从A到C(在A加油站加好油)，或者到B后还能再前进一段距离。也就是在加油站少加点油能够支撑到C就可。  
哇，这么一想，好复杂啊～～到底该加多少油呢？？  
我们可以这么想，在A加油站一升一升的加油，加一升油看是否能够到达下一个城市B，不够的话再加，直到加到能到达为止，而到达下一个城市B后，现在有两种选择，是选择B城市的油加油，还是选择A城市的油加油，这就看谁花费的少了，谁花费少就加谁的油。现在油箱中的油刚好够到达下一个城市C，但还没达到油箱的最大容量。还是一升一升的向油箱中加油，加一升油看是哪里的花费低。直到加到能够到达下下个城市为止。当然到达B后油箱中的油会少的。  
看，这么推，就推出了一种状态，我们可以使用一个二元组(city,fuel)来表示每个状态，其中city为城市编号，fuel为油箱中剩余的汽油，使用一个二元数组d\[city\]\[fuel\]来存储最少花费。它表示从起点到达city城市后剩余油量fuel的最少花费是d\[city\]\[fuel\]。  
现在再来解释下在B城市加油的选择，到达B后的状态是d\[A\]\[10\],(假设A到B的路径长是10)，现在要向城市C出发，需要向油箱中加油，如果油箱中的油量还没到达到油箱的容量，加一升油现在状态变为d\[A\]\[11\],还有一种状态那就是d\[B\]\[1\]，在B处加油，前面d\[A\]\[11\]指的是在A处多加一升油，这样可以在B处少加一升，如果多加的这一升油价钱比B处的少的话，那就选择在A处加油，否则选在在B处。  
建立一个小根堆来保存当前花费状态，不断取出优先队列中“当前花费最少”的状态进行拓展，更新拓展到的新状态在记录数组d中存储的值，直到终点T的某个状态第一次被取出，即可停止BFS，输出答案。

#include <iostream>
    #include <algorithm>
    #include <queue>
    #include <vector> 
    using namespace std;
    const int INF = 0x3f3f3f3f;
    int n,m; // 城市 道路
    bool flag = false;
    struct City{ 
        int v; // 城市
        int d; // 长度
        City(int v,int d):v(v),d(d){ }
    };
    
    struct Cost{ 
        int city; // 到达的城市
        int fuel; // 剩余油量
        int costs; // 花费
        Cost(int c,int f,int costs):city(c),fuel(f),costs(costs){ }
        bool operator < (const Cost b) const{ 
            return costs > b.costs;
        }
    };
    int price[1005]; // 油价
    int dp[1005][101]; // 状态，到达城市i，剩余油量j的最小花费
    vector<City> vec[10005]; // 邻接表
    bool visited[1005][105]; // 标记被访问的状态
    void Query(int c, int s, int e){ 
        priority_queue<Cost> q; //建立小根堆，优先输出花费最小
        q.push(Cost(s,0,0));
        dp[s][0] = 0;
        while(!q.empty()){ 
            Cost x = q.top();
            q.pop();
            int a = x.city; // 当前的城市
            int b = x.fuel; // 当前油箱中的油量
            if(visited[a][b]) continue; // 该状态访问过
            if(x.city == e){ 
                cout << x.costs <<endl;
                flag = true;
                break;
            }
            if(b < c){  // 加油,准备下一次旅行
                if(dp[a][b] + price[a] < dp[a][b + 1]){ 
                    dp[a][b + 1] = dp[a][b] + price[a];
                    q.push(Cost(a,b + 1,dp[a][b + 1]));
                }
            }
            for(int i = 0; i < (int)vec[a].size(); i++){ 
                int d = vec[a][i].d;
                int v = vec[a][i].v;
                if(b - d >= 0 && dp[a][b] < dp[v][b - d]){  // 这里也防止了油量溢出
                    dp[v][b - d] = dp[a][b];
                    q.push(Cost(v,b - d, dp[v][b - d]));
                }
            }
            visited[a][b] = true;
        }
    }
    int main(){ 
        cin >> n >> m;
        for(int i = 0;i < n; i++){ 
            cin >> price[i];
        }
        for(int i = 0;i < m; i++){ 
            int u,v,d;
            cin >> u >> v >> d;
            vec[u].push_back(City(v,d));
            vec[v].push_back(City(u,d));
        }
        int t; // 查询次数
        cin >> t;
        while(t--){ 
            int C,s,e; // 油箱容量，起点，终点
            cin >> C >> s >> e;
            memset(visited,false,sizeof(visited));
            for(int i = 0;i <= n;i++){ 
                for(int j = 0;j <= C;j++){ 
                    dp[i][j] = INF;
                }
            }
            flag = false;
            Query(C,s,e);
            if(flag == false) cout << "impossible" << endl;
        }
        return 0;
    }

[poj-3635.Full Tank]: http://poj.org/problem?id=3635