Full Tank?
Description After going through the receipts from your car trip through Europe this summer, you realised that the gas prices varied between the cities you visited. Maybe you could have saved some money if you were a bit more clever about where you filled your fuel? To help other tourists (and save money yourself next time), you want to write a program for finding the cheapest way to travel between cities, filling your tank on the way. We assume that all cars use one unit of fuel per unit of distance, and start with an empty gas tank. Input The first line of input gives 1 ≤ n ≤ 1000 and 0 ≤ m ≤ 10000, the number of cities and roads. Then follows a line with n integers 1 ≤ pi ≤ 100, where pi is the fuel price in the ith city. Then follow m lines with three integers 0 ≤ u, v < n and 1 ≤ d ≤ 100, telling that there is a road between u and v with length d. Then comes a line with the number 1 ≤ q ≤ 100, giving the number of queries, and q lines with three integers 1 ≤ c ≤ 100, s and e, where c is the fuel capacity of the vehicle, s is the starting city, and e is the goal. Output For each query, output the price of the cheapest trip from s to e using a car with the given capacity, or "impossible" if there is no way of getting from s to e with the given car. Sample Input 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 Sample Output 170 impossible Source |
题意:给出一张图,n<=1000,m<=10000. 有一辆车想从图的一个地方到达另外一个地方,每个点是一个卖油的地方,每个地方买的有价格不一样,车的最大装油量是c,求初始点到终止点的最小花费。
网上大部分的思路都是类似于dij的那种扩展。
首先定义一个二维数组dp。 dp[i][j] 表示走到i点剩余j个单位的汽油时的最小花费
然后维护一个优先队列。 每次有两种可扩展的状态,一是加一个单位的油,二是走向邻接点,然后不断的将状态加入优先队列中
【题意】
给你 n 个点,m 条边,每走 1 单位的路径都会花费 1 单位的 fuel ,并且不同的点灌油的油的价格是不同的,现在给你一些询问,每一个询问给你起点、终点以及油箱的容量,问你所需要的最少的花费可以从起点到达终点。
涉及两个维的图最短路,一个是费用,一个是地点。(比如在位置0有1升油是一个点,在位置0有2升油又是另外一个点)
如果把这个点抽象出来,把费用看过边,那么最少费用就可以类似dijsktra算法那样不断的加入点。
于是得到一个扩展结点的策略:
1.每一次加一升油(因为题目的条件这些都是整数,所以可以类似离散化处理,一点一点加入油)
2.如果加的油足够走到下一个结点,那就走到下一个结点吧(记得减去路上消耗的油,还有花费不变…)
(至于在第二次扩展时要不要加油,这个就不需要了.因为在第一种情况扩展结点的时候加油了…)
这里的BFS是把所有可扩展的节点都加入优先队列中,而Dijkstra是每次松弛了的点才加入,中间少了很多状态。但是思想都是一样的。不知道这题能不能像Dij那样做。
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; const int VM=1010; const int EM=10010; const int INF=0x3f3f3f3f; struct Edge{ int to,nxt; int cap; }edge[EM<<1]; struct Status{ int u,fuel,cost; bool operator < (const Status &a) const{ return a.cost<cost; } }; int n,m,cnt,head[VM],price[VM]; priority_queue<Status> q; int vis[VM][110]; void addedge(int cu,int cv,int cw){ edge[cnt].to=cv; edge[cnt].cap=cw; edge[cnt].nxt=head[cu]; head[cu]=cnt++; edge[cnt].to=cu; edge[cnt].cap=cw; edge[cnt].nxt=head[cv]; head[cv]=cnt++; } void push_q(int u,int f,int c){ Status cur; cur.u=u; cur.fuel=f; cur.cost=c; q.push(cur); } int BFS(int c,int s,int e){ memset(vis,0,sizeof(vis)); while(!q.empty()) q.pop(); push_q(s,0,0); Status cur; while(!q.empty()){ cur=q.top(); q.pop(); int u=cur.u, fuel=cur.fuel, cost=cur.cost; vis[u][fuel]=1; if(u==e) return cost; //每次有两种可扩展的状态,如下: if(fuel<c && !vis[u][fuel+1]) //一是加一个单位的油 push_q(u,fuel+1,cost+price[u]); for(int i=head[u];i!=-1;i=edge[i].nxt) //二是走向邻接点,然后不断的将状态加入优先队列中 if(fuel>=edge[i].cap && !vis[edge[i].to][fuel-edge[i].cap]) push_q(edge[i].to,fuel-edge[i].cap,cost); } return -1; } int main(){ //freopen("input.txt","r",stdin); while(~scanf("%d%d",&n,&m)){ cnt=0; memset(head,-1,sizeof(head)); for(int i=0;i<n;i++) scanf("%d",&price[i]); int u,v,w; while(m--){ scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); } int q,c,s,e; scanf("%d",&q); while(q--){ scanf("%d%d%d",&c,&s,&e); int ans=BFS(c,s,e); if(ans==-1) printf("impossible\n"); else printf("%d\n",ans); } } return 0; }
相关推荐
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
因为考虑到通过砖墙时和空地所花的时间不同,所以不能使用一般的BFS广搜来做。用DFS深搜,你会发现时间复杂非常高,必然会超时(最大是300*300的图)。本题可以使用改进过的广搜或优先队列+bfs 或 记忆化广搜三种...
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
北大POJ初级-所有题目AC代码+解题报告
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ3373-Changing Digits【DFS+强剪枝】 解题报告+AC代码
POJ2186-Popular Cows 【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
北大POJ3414-Pots 解题报告+AC代码
北大POJ1004-Financial Management 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ初级-简单搜索 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ2187-Beauty Contest 解题报告+AC代码
北大POJ1159-Palindrome 解题报告+AC代码
北大POJ3252-Round Numbers 解题报告+AC代码
北大POJ1416-Shredding Company 解题报告+AC代码
北大POJ1163-The Triangle 解题报告+AC代码
北大POJ1019-Number Sequence 解题报告+AC代码