首页 > 代码库 > poj 3635 Full Tank? ( 图上dp )
poj 3635 Full Tank? ( 图上dp )
题意:
已知每个点的加油站的油价单价(即点权),每条路的长度(边权)。
有q个询问,每个询问包括起点s、终点e和油箱容量。
问从起点走到终点的最小花费。如果不可达输出impossible,否则输出最小的旅途费用。
算法:
其实要分析状态= =感觉就像是dp。
最直接的想法是 每到一个点都加上要走到下一个点所需要的油量。但是走的路不同,到底怎么处理加多少的问题呢?
因此想到分解状态,即拆点。每到一个点都+1单位的油量,然后把这个状态加入队列。另外如果现在油箱内的油足够达到下一点,
则更新状态,把新状态加入优先队列。
dp[i][j]表示到第i个城市剩余油量为j的花费。
简单的说,就是优先队列优化的最短路算法多了一维。
为了把所有可能的状态考虑到,
每到一个点只有两种操作:1、加一单位的油 2、更新能走到的下一个点。
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<queue> #define maxm 10010 #define maxn 1010 using namespace std; struct Edge { int to,val,next; }edge[maxm*2]; struct node { int id,cost,oil; bool operator <(const node &b) const { return cost > b.cost; } }; bool vis[maxn][110]; int cnt,head[maxn],dp[maxn][110],ans,st,ed,cap,p[maxn]; priority_queue<node> q; void add(int x,int y,int z) { edge[cnt].to = y; edge[cnt].val = z; edge[cnt].next = head[x]; head[x] = cnt++; } bool bfs() { memset(dp,0x3f,sizeof(dp)); memset(vis,0,sizeof(vis)); while(!q.empty()) q.pop(); int id,oil,cost; ans = 0; dp[st][0] = 0; node now,cur,next; now.id = st; now.cost = 0; now.oil = 0; q.push(now); while(!q.empty()) { cur = q.top(); q.pop(); id = cur.id,oil = cur.oil,cost = cur.cost; if(id == ed) { ans = cost; return true; } if(vis[id][oil]) continue; vis[id][oil] = true; if(oil < cap) { next.id = id; next.cost = cost+p[id]; next.oil = oil+1; if(dp[next.id][next.oil]>next.cost && !vis[next.id][next.oil]) { dp[next.id][next.oil] = next.cost; q.push(next); } } for(int i=head[id];i!=-1;i = edge[i].next) { int u = edge[i].to; int w = edge[i].val; if(oil>=w && dp[u][oil-w]>cur.cost && !vis[u][oil-w]) { next.oil = oil-w; next.id = u; next.cost = cost; dp[u][next.oil] = next.cost; q.push(next); } } } return false; } int main() { int n,m,u,v,l,que; while(scanf("%d%d",&n,&m)!=EOF) { memset(head,-1,sizeof(head)); cnt = 0; for(int i=0;i<n;i++) scanf("%d",&p[i]); for(int i=0;i<m;i++) { scanf("%d%d%d",&u,&v,&l); add(u,v,l); add(v,u,l); } scanf("%d",&que); while(que--) { scanf("%d%d%d",&cap,&st,&ed); if(bfs()) printf("%d\n",ans); else printf("impossible\n"); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。