JLOI2011 飞行路线-白红宇

JLOI2011 飞行路线

阅读量：5337 次

发布时间：2019-06-15

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

分层图\(SPFA\)……听起来好高级的样子……嗯，所以我选分层图\(\rm{dijkstra}\)

o_QQ%e6%88%aa%e5%9b%be20180801193256.png

这题好像是会卡\(SPFA\)，要加一个玄学\(SLF\)优化才可以……

所以还是用堆优化\(\rm{dijkstra}\)吧，多好 o_QQ%e5%9b%be%e7%89%8720180623180015.png

以上全是瞎扯，但卡\(SPFA\)是真的

用\(\tt{dis[i][j]}\)表示免费乘坐了\(i\)次到达点\(j\)的最小代价，跑最短路的时候顺推下来就可以了

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;int read(){    int k=0; char c=getchar();    for(;c<'0'||c>'9';) c=getchar();    for(;c>='0'&&c<='9';c=getchar())      k=(k<<3)+(k<<1)+c-48;    return k;}struct zzz{    int t,len,nex;}e[50010<<1]; int head[10010],tot;void add(int x,int y,int z){    e[++tot].t=y;    e[tot].len=z;    e[tot].nex=head[x];    head[x]=tot;}int dis[21][10010];struct hhh{    int v,cnt,pos;    bool operator < (const hhh &y) const{        return v > y.v;    }};priority_queue 
         
           q;void dijkstra(int s,int num){ memset(dis,127,sizeof(dis)); dis[0][s]=0; q.push(hhh{0,0,s}); while(!q.empty()){ hhh k=q.top(); q.pop(); if(dis[k.cnt][k.pos]!=k.v) continue; for(int i=head[k.pos];i;i=e[i].nex){ int to=e[i].t; if(dis[k.cnt][to]>dis[k.cnt][k.pos]+e[i].len){ dis[k.cnt][to]=dis[k.cnt][k.pos]+e[i].len; q.push(hhh{dis[k.cnt][to],k.cnt,to}); } if(k.cnt+1<=num&&dis[k.cnt][k.pos]