BZOJ 3627 JLOI 2014 路径规划分层图 SPFA+HEAP-白红宇的个人博客

BZOJ 3627 JLOI 2014 路径规划分层图 SPFA+HEAP

发布日期：2021-10-02 10:57:38 浏览次数：23 分类：技术文章

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

题目大意：N个点M条无向边，每个点有可能有红绿灯，或者是加油站，或者单单是一个点。红绿灯太多会让人烦，太久不加油车子就会开不动，问最多通过K次红绿灯，从“start”点到“end”点的最少花费是多少。

思路：只能最多通过K次红绿灯，可以依据这个建分层图。f[ i ][ j ]为在已经通过i次红绿灯后，在j点时的最小花费。这只是总体的思路，具体是实现起来还是有其他一些小问题。

题目中有一个limit，表示从一个加油站到另一个加油站不能行驶超过这么远。仔细想想，其实那些不是加油站的点对我们来说没什么意义。经过简单的处理即可把他们处理掉。以每个加油站为起点进行SPFA，计算出这个节点到其他节点的距离和经过了多少红绿灯。把这些信息加入新图中，再从起点到终点跑一次SPFA就可以得到答案。

另外，红绿灯的等待时间取得是数学期望，简单画图像可得time = (red * red) / (2 * (red + green))

CODE：

#include #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define MAX 100010#define INF 0x7f7f7f7fusing namespace std;map
           
             G;map
            
              gas_num;double f[11][MAX];bool v[11][MAX];struct Complex{ int pos,step; Complex(int _step,int _pos):pos(_pos),step(_step) {} Complex() {} bool operator <(const Complex& a)const { return f[step][pos] > f[a.step][a.pos]; }};int points,edges,k,limit,cost;int st,ed;int total_gas;double expection[MAX];bool stop[MAX],is_gas[MAX];int head[MAX],total;int next[MAX],aim[MAX];double length[MAX];int _head[MAX],_total;int _next[MAX],_aim[MAX];int lights[MAX];double _length[MAX];string temp;inline void Add(int x,int y,double len);inline void _Add(int x,int y,double _len,int l);inline void _SPFA(int start);void SPFA();int main(){ cin >> points >> edges >> k >> limit >> cost; for(int x,y,i = 1;i <= points; ++i) { cin >> temp; G[temp] = i; if(temp == "start") st = i,is_gas[i] = true; if(temp == "end") ed = i,is_gas[i] = true; if(temp.find("gas") != string::npos) is_gas[i] = true; scanf("%d%d",&x,&y); if(x) { expection[i] = (double)(x * x) / (2.0 * (x + y)); stop[i] = true; } } for(int x,y,len,i = 1;i <= edges; ++i) { cin >> temp; x = G[temp]; cin >> temp; y = G[temp]; cin >> temp >> len; Add(x,y,(double)len + expection[y]),Add(y,x,(double)len + expection[x]); } for(int i = 1;i <= points; ++i) if(is_gas[i]) _SPFA(i); SPFA(); double ans = INF; for(int i = 0;i <= k; ++i) ans = min(ans,f[i][ed]); cout << fixed << setprecision(3) << ans - cost; return 0;}inline void Add(int x,int y,double len){ next[++total] = head[x]; aim[total] = y; length[total] = len; head[x] = total;}inline void _Add(int x,int y,double len,int l){ _next[++_total] = _head[x]; _aim[_total] = y; _length[_total] = len; lights[_total] = l; _head[x] = _total;}inline void _SPFA(int start){ static priority_queue
             
               q; while(!q.empty()) q.pop(); memset(f,0x43,sizeof(f)); memset(v,false,sizeof(v)); f[0][start] = 0; q.push(Complex(0,start)); while(!q.empty()) { Complex temp = q.top(); q.pop(); int x = temp.pos,step = temp.step; v[step][x] = false; for(int i = head[x];i;i = next[i]) { bool detla = stop[aim[i]]; if(step + detla <= k && f[step + detla][aim[i]] > f[step][x] + length[i]) { f[step + detla][aim[i]] = f[step][x] + length[i]; if(!v[step + detla][aim[i]]) { v[step + detla][aim[i]] = true; q.push(Complex(step + detla,aim[i])); } } } } for(int i = 0;i <= k; ++i) for(int j = 1;j <= points; ++j) if(j != start && f[i][j] <= limit && is_gas[j]) _Add(start,j,f[i][j] + cost,i);}void SPFA(){ static priority_queue
              
                q; memset(f,0x43,sizeof(f)); memset(v,false,sizeof(v)); f[0][st] = 0; q.push(Complex(0,st)); while(!q.empty()) { Complex temp = q.top(); q.pop(); int x = temp.pos,step = temp.step; v[step][x] = false; for(int i = _head[x];i;i = _next[i]) if(step + lights[i] <=k && f[step + lights[i]][_aim[i]] > f[step][x] + _length[i]) { f[step + lights[i]][_aim[i]] = f[step][x] + _length[i]; if(!v[step + lights[i]][_aim[i]]) { v[step + lights[i]][_aim[i]] = true; q.push(Complex(step + lights[i],_aim[i])); } } }}

转载地址：https://blog.csdn.net/jiangyuze831/article/details/39207281 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：BZOJ 2662 BeiJing wc2012 冻结

下一篇：BZOJ 2763 JLOI 2011 飞行路线分层图+最短路

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章