Uva(11367)(Full Tank)

链接：https://vjudge.net/problem/UVA-11367
思路：这是一个dijkstra+dp的问题，将dijkstra中的d改为二维，并以花费作为排序目标，然后进行dp，dp的时候可以回忆一下01背包滚动数组的dp方式，从右往左进行选择，即以单位油为状态进行选择。代码中我会详细解释
代码：

#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;

typedef pair<int,int> P;

int n,m;
const int maxn = 1010;
int cost[maxn];

struct edge{
    int from;int to;int dist;
    edge(){}
    edge(int f,int t,int d):from(f),to(t),dist(d){};
};

//表示状态，cost表示当前花费，f表示剩下的油量，id表示当前在哪个站
struct node{
    int cost,f,id;
    node(){}
    node(int c,int i,int ff){
        cost = c;
        id = i;
        f = ff;
    }
    bool operator<(const node &r)const{
        return cost>r.cost;
    }
};

struct Dijsktra{
vector<int> G[maxn];
vector<edge> edges;
int d[maxn][100];
int p[maxn];
int n,m;

void init(int n){
    this->n = n;
    for(int i=0;i<=n;i++)G[i].clear();
        edges.clear();
}

void addedge(int from,int to,int dist){
    edges.push_back(edge(from,to,dist));
    m = edges.size();
    G[from].push_back(m-1);
}

int dijsktra(int c,int s,int e){
    priority_queue<node> qq;
    qq.push(node(0,s,0));
    for(int i=0;i<n;i++)
for(int j=0;j<=100;j++)
        d[i][j] = 1e9;
d[s][0] = 0;
while(!qq.empty()){
    node p1 = qq.top();
    qq.pop();
    int u = p1.id;
    int f1 = p1.f;
    if(u==e)return p1.cost;//到达查询终点就可以跳出，不需要把每个点都算出来
    if(d[u][f1]<p1.cost)continue;
    for(int i=0;i<G[u].size();i++){
        edge &e = edges[G[u][i]];
//01背包二维滚动数组的变形，从右往左进行状态更新，注意下届是当前油量和下一条边距离的较大值，自行理解一下，可以囊括所有状态
        for(int j=c;j>=max(f1,e.dist);j--){
            if(d[e.to][j-e.dist] > d[u][f1]+(j-f1)*cost[u]){
            d[e.to][j-e.dist] = d[u][f1]+(j-f1)*cost[u];
            qq.push(node(d[e.to][j-e.dist],e.to,j-e.dist));
        }
        }
    }
}
return -1;
}

}solver;

int main(){
    scanf("%d%d",&n,&m);
    solver.init(n);
    for(int i=0;i<n;i++)scanf("%d",&cost[i]);
    for(int i=0;i<m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        solver.addedge(a,b,c);
        solver.addedge(b,a,c);
    }
    int q;
    scanf("%d",&q);
    while(q--){
        int c,s,e;
        scanf("%d%d%d",&c,&s,&e);
        int res = solver.dijsktra(c,s,e);
        if(res==-1)printf("impossible\n");//无解
        else{
            printf("%d\n",res);
        }
    }
    return 0;
}