原题链接
更好的阅读体验

题目描述

有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

优先队列+BFS(dijiskla)

看到上面标黑的字,相信给位已经很清楚了这道题目就是一道最短路的题目.

但是这道题目只是用到了思想,我们实现方法还是优先队列+BFS,首先我们可以开一个二元组(city,fuel)表示状态,city为城市编号,fuel为剩余的汽油量,既然这样的话,我们的起始状态就是(S,0).

接下来就是两种可选择的方案

1. 如果说当前fuel<C,还没有装满油的话,那么我们可以选择加一升汽油,然后拓展到新的状态,也就是(city,fuel+1)
2. 对于每一条边而言,我们可以通过这条边到达一个城市,那么如果说当前剩余油量可以走完这条路,那么我们就拓展新状态(Next,fuel-w)

综上所述,我们不断地取出当前花费最少的状态进行拓展,然后每一次拓展用ans数组记录最小花费即可.具体可看代码实现

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N=1010;
const int M=10100;
int wn[N],head[N],Next[2*M],ver[2*M],dis[2*M],ans[N][102];
bool vis[N][102];
int c,s,e,n,m,t,tot=-1;
void add(int x,int y,int z)//链式前向星
{
    ver[++tot]=y;//这条边到达的点
    Next[tot]=head[x];//链接
    dis[tot]=z;//权值
    head[x]=tot;//标记x起点
}
struct node
{
    int u,f,w;
    node(int x,int y,int z):u(x),f(y),w(z) {}
    friend bool operator < (node a,node b)
    {
        return a.w>b.w;//权值从小到大排序,记住是小根堆
    }
};
priority_queue <node> q;
bool check1(int u,int f)
{
    if(f+1<=c && !vis[u][f+1] && (ans[u][f+1]>ans[u][f]+wn[u]))//如果油还在油箱限制内,且这买油一定更好的话
        return 1;
    return 0;
}
bool check2(int f,int v,int p,int w)
{
    if(f>=p && !vis[v][f-p] && ans[v][f-p]>w)//如果说当前这个点没有访问过,且当前剩余油大于路径花费油
        return 1;
    return 0;
}
int BFS()
{
    while(!q.empty())
        q.pop();
    memset(vis,false,sizeof(vis));
    memset(ans,0x3f,sizeof(ans));
    ans[s][0]=0;
    q.push(node(s,0,0));//s为起点,0为剩余油量,0为权值
    while(!q.empty())
    {
        node now=q.top();
        q.pop();
        int u=now.u;
        int f=now.f;
        int w=now.w;
        vis[u][f]=true;//访问过了
        if(u==e)//到达终点了
            return w;
        if(check1(u,f))//判断
        {
            ans[u][f+1]=ans[u][f]+wn[u];//加上一升油的钱
            q.push(node(u,f+1,ans[u][f+1]));//购买一升油的状态
        }
        for(int i=head[u]; i; i=Next[i])//遍历
        {
            int v=ver[i],p=dis[i];
            if(check2(f,v,p,w))//判断
            {
                ans[v][f-p]=w;//耗费油
                q.push(node(v,f-p,w));
            }
        }
    }
    return -1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=0; i<n; i++)
        cin>>wn[i];
    for(int i=1; i<=m; i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
        add(y,x,z);//无向图两条边
    }
    cin>>t;
    while(t--)
    {
        cin>>c>>s>>e;
        int ans=BFS();
        if(ans==-1)
            printf("impossible\n");//无解
        else
            printf("%d\n",ans);
    }
    return 0;
}