注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

DJ+堆和系统队列用法  

2014-10-29 15:28:35|  分类: C++ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
#include<cstdio>
#include<queue>
#include<cstring>
#define nn 100010
#define pii pair<ll,int> 
#define mk make_pair
#define x first
#define y second
using namespace std;
/*struct node{
  int x,y;
  bool operator <(const node&b)const{
    return x>b.x;
  }
};
priority_queue<node>QQ;多种*/ 

//priority_queue<int,vector<int>,less<int> >Q;//单个排序; 
typedef int ll;
struct node{int end,next,s;
}g[nn*4];
priority_queue<pii>Q;//pair
int n,m,u,t,tot,j,c,k,i,z,x,y;
int fa[nn],blink[nn];
int dis[nn][32],ans;
int min(int a,ll b){return (a>b)?b:a;}

void DJ()
 {pii z;
  while (!Q.empty()){
  z=Q.top();Q.pop();
  for (int i=fa[z.y];i;i=g[i].next)
     {int u=g[i].end;
      if (dis[u][t]>z.x*-1+g[i].s&&(z.x*-1+g[i].s>0))
         {dis[u][t]=z.x*-1+g[i].s;
          Q.push(mk(dis[u][t]*-1,u));
         }
     }
                    }
 }
 
void add(int a,int b,int c)
 {g[++tot].end=b;g[tot].next=fa[a];
  g[tot].s=c;fa[a]=tot;
 } 
 
int main()
{
 freopen("bst.in","r",stdin);
 freopen("bst.out","w",stdout);
 scanf("%d%d%d%d",&n,&m,&c,&k);
 for (i=1;i<=k;i++)scanf("%d",&blink[i]);
 while (m--){scanf("%d%d%d",&x,&y,&z); 
             add(x,y,z);
             add(y,x,z);
            }
  memset(dis,0x7f,sizeof(dis));
 dis[1][0]=0;t=0;
 Q.push(mk(0,1));
 DJ();
 while (c--){ 
 for (i=1;i<=k;i++){
  
  x=blink[i];
  for (j=fa[x];j;j=g[j].next)
     {u=g[j].end;
      if (dis[x][t]<dis[u][t+1])
      dis[u][t+1]=dis[x][t],Q.push(mk(dis[u][t+1]*-1,u));
     }
                   }
  t++;
  DJ();
            }
 ans=0x7fffffff;
 for (i=0;i<=t;i++)ans=min(ans,dis[n][i]);
 printf("%d\n",ans);
 return 0;
}

  评论这张
 
阅读(180)| 评论(3)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018