POJ 3635 Full Tank?-白红宇

POJ 3635 Full Tank?

阅读量：6238 次

发布时间：2019-06-22

本文共 1827 字，大约阅读时间需要 6 分钟。

题意：告诉你n个城市的油价和m条道路的距离。Q次询问，告诉你出发点，目的地以及油箱的最大容量，要求问答最少花费是多少。

思路：参考了网上的思路http://blog.csdn.net/sdj222555/article/details/7693093 SPFA+优先队列

用类似于dp的思想，dp[i][j]表示到达第i个城市剩余j升油的最小花费。维护一个优点队列，一开始我的思路是对于当前节点相连的每一条边从边的长度开始+1直到加到油箱容量的限制，然后把所有的点入队

然后这样做爆栈了。然后只能参考网上的思路，把当前的油量加1入队，然后如果可以到达下一个节点，就把下一个节点入队，当然要减去边的花费。可是这个时候TLE了。因为我进行了一次完整的SPFA。因为

我们维护的是一个优先队列，所以当目的节点第一次出队的时候，必然就是最小值，即我们所求的答案。然后终于A了。407MS水过。

在这个题还学会了自定义结构体的优先队列使用。参考了博客http://blog.csdn.net/dooder_daodao/article/details/5761550

在初始化结构体的优先队列时需要要再定义一个cmp结构体作为比较。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             using namespace std;const int INF=0x3f3f3f3f;const int MAXN=1100;const int MAXM=110000;int val[MAXN];int n,m,u,v,w,q,cc,ss,ee,tot;int dp[MAXN][110];int head[MAXN];struct Edge{ int v,w,nex;}edge[MAXM*2];struct Node{ int cost,u,lef;};struct cmp{ bool operator()(Node a,Node b) { return a.cost>b.cost; }};void addedge(int u,int v,int w){ edge[tot].v=v; edge[tot].w=w; edge[tot].nex=head[u]; head[u]=tot++; edge[tot].v=u; edge[tot].w=w; edge[tot].nex=head[v]; head[v]=tot++;}void init(){ tot=0; memset(head,-1,sizeof(head));}priority_queue
             
              
               ,cmp> que;void SPFA(){ for(int i=0;i
               
                u.cost+val[u.u]) { node.u=u.u; node.cost=u.cost+val[u.u]; node.lef=u.lef+1; que.push(node); } for(int i=head[u.u];i!=-1;i=edge[i].nex) { Edge e=edge[i]; if(e.w>u.lef) continue; node.cost=u.cost; node.u=e.v; node.lef=u.lef-e.w; que.push(node); /* for(int j=max(u.lef,e.w);j<=cc;j++) { Node node; node.cost=u.cost+(j-u.lef)*val[u.u]; node.u=e.v; node.lef=j-e.w; que.push(node); } */ } }}int main(){ freopen("in.txt","r",stdin); while(scanf("%d%d",&n,&m)!=EOF) { init(); for(int i=0;i

View Code

转载于:https://www.cnblogs.com/onlyAzha/p/4769961.html

你可能感兴趣的文章