176. 装满的油箱（bfs）

朱雀 2021-11-11 00:28 184阅读 0赞

题目链接：[https://www.acwing.com/problem/content/description/178/][https_www.acwing.com_problem_content_description_178]

有N个城市（编号0、1…N-1）和M条道路，构成一张无向图。

在每个城市里边都有一个加油站，不同的加油站的单位油价不一样。

现在你需要回答不超过100个问题，在每个问题中，请计算出一架油箱容量为C的车子，从起点城市S开到终点城市E至少要花多少油钱？  
输入格式

第一行包含两个整数N和M。

第二行包含N个整数，代表N个城市的单位油价，第i个数即为第i个城市的油价pi

。

接下来M行，每行包括三个整数u,v,d，表示城市u与城市v之间存在道路，且车子从u到v需要消耗的油量为d。

接下来一行包含一个整数q，代表问题数量。

接下来q行，每行包含三个整数C、S、E，分别表示车子油箱容量、起点城市S、终点城市E。  
输出格式

对于每个问题，输出一个整数，表示所需的最少油钱。

如果无法从起点城市开到终点城市，则输出”impossible”。

每个结果占一行。  
数据范围

1≤N≤1000  
,  
1≤M≤10000,  
1≤pi≤100,  
1≤d≤100,  
1≤C≤100

输入样例：

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

输出样例：

170  
impossible

分析：  
首先，根据题意，我们肯定是要考虑在每个结点剩余不同油量的情况。

所以我们定义一个三元组\{vex，fuel，cost\} 表示到达vex这个城市，还剩余fuel油量，并且花费为cost。同时定义一个dp\[vex\]\[fuel\]表示到达vex这个城市，剩余fuel油量的时候的最少花费。

定义完成后，开始考虑初始状态。dp数组初始状态肯定都是INF（因为dp数组存储的是最少花费）。然后三元组一开始一定为\{S，0，0\}。表示车子在开始城市S的时候原始状态。  
现在考虑如何转移这个三元组。  
第一，如果三元组里面的 油量fuel，足够走（S，v）（表示S号城市和v号城市之间有路）这条路线，那么我们可以尝试在这条路线，并把状态加入到优先队列中。新的状态应该为\{V，fuel-fuel\_cost,cost\}.  
第二，我们还可以在当前的城市加一点油，这也是一个状态。很明显，我们每次油量应该+1，得到新状态\{S，fuel+ 1,cost+w\[S\]\}。因为每次+1，必然会得到在这个城市油被加满的情况。

答案是求到达E号城市的最少花费。  
我们完全可以用优先队列来不断的更新。  
一开始的状态时\{S，0，0\}。我们会将这个状态能转移到的状态全部加入优先队列中，那么更新完后，我们应该怎样继续更新呢？很明显，我们应该继续选择花费最少的那个状态更新，因为你如果选择了花费大的更新，那么更新得到的值一定不是最优的，会导致更新得到的值需要重新被更新。会超时。  
从花费最少的那个状态继续更新，更新的得到的值也一定是最优的了。

#include"stdio.h"
    #include"string.h"
    #include"queue"
    #include"vector"
    #include"algorithm"
    using namespace std;
    #define INF 1001010
    typedef pair<int,int> PII;
    
    typedef struct Node
    {
        int vex;
        int fuel;
        int cost;
        Node(int a,int b,int c)
        {
            vex = a; fuel = b; cost = c;
        }
        Node(){}
        friend bool operator < (Node x,Node y)
        {
            return x.cost > y.cost;
        }
    }Node;
    
    int N,M;
    int w[1010];
    int dp[1010][110];
    int vis[1010][110];
    vector<PII> Graph[1010];
    int S,E,C;
    
    void init()
    {
        for(int i = 0; i < 1010; i ++)
            for(int j = 0; j < 110; j ++)
               {
                   dp[i][j] = INF;
                   vis[i][j] = 0;
               }
        dp[S][0] = 0;
    }
    
    int check1(Node T)
    {
        int v = T.vex;
        int ful = T.fuel;
        int p = T.cost;
        if(ful + 1 <= C && vis[v][ful + 1] == 0 && dp[v][ful + 1] > p + w[v])
            return 1;
        return 0;
    }
    
    int check2(int u,int ful_cost,int ful,int p)
    {
        if(ful_cost <= ful && vis[u][ful - ful_cost] == 0 && dp[u][ful - ful_cost] > p)
            return 1;
        return 0;
    }
    int bfs()
    {
        priority_queue<Node> Q;
        Q.push({S,0,0});
        while(!Q.empty())
        {
            Node T = Q.top(); Q.pop();
            int v = T.vex;
            int ful = T.fuel;
            int p = T.cost;
            if(v == E) return p;
            vis[v][ful] = 1;
            if(check1(T) == 1)
            {
                dp[v][ful + 1] = p + w[v];
                Q.push({v,ful + 1,dp[v][ful + 1]});
            }
            for(int i = 0; i < Graph[v].size(); i ++)
            {
                int u = Graph[v][i].first;
                int ful_cost = Graph[v][i].second;
                if(check2(u,ful_cost,ful,p))
                {
                    dp[u][ful - ful_cost] = p;
                    Q.push({u,ful - ful_cost,p});
                }
            }
        }
        return -1;
    }
    
    int main()
    {
        scanf("%d%d",&N,&M);
        for(int i = 1; i <= N; i ++)
            scanf("%d",&w[i]);
        for(int i = 1; i <= M;i ++)
        {
            int u,v,d;
            scanf("%d%d%d",&u,&v,&d);
            u ++; v ++;
            Graph[u].push_back({v,d});
            Graph[v].push_back({u,d});
        }
        int q;
        scanf("%d",&q);
        while(q --)
        {
            scanf("%d%d%d",&C,&S,&E);
            S ++; E ++;
            init();
            int minx = bfs();
            if(minx == -1)
                printf("impossible\n");
            else
                printf("%d\n",minx);
        }
    }

[https_www.acwing.com_problem_content_description_178]: https://www.acwing.com/problem/content/description/178/