Uva(11367)(Full Tank)
2018-08-14 本文已影响0人
kimoyami
链接: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;
}