单源最短路模板_SPFA_Dijkstra（堆优化）

　　随手一打就是标准的SPFA，默认1号节点为出发点，当然不用 f 判断是否在队里也可以，只是这样更优化一点

 void spfa()

 {

     int i,x,k;

     for (i=;i<=n;i++)

     {

         d[i]=oo;

         f[i]=;

     }

     d[]=;

     q.push();

     while (!q.empty())

     {

         x=q.front();

         q.pop();

         f[x]=;

         for (i=first[x];i;i=next[i])

         {

             k=v[i];

             if (d[k]>d[x]+w[i])

             {

                 d[k]=d[x]+w[i];

                 if (f[k])

                 {

                     q.push(k);

                     f[k]=;

                 }

             }

         }

     }

 }

　　Dijkstra+堆优化，调了我3个多小时终于调到正确的最优的模板

 void down(int x)

 {

     x<<=;

     if (x>t) return;

     if (x<t&&d[s[x+]]<d[s[x]]) x++;

     if (d[s[x]]>=d[s[x>>]]) return;

     swap(s[x],s[x>>]);

     swap(p[s[x]],p[s[x>>]]);

     down(x);

 }

 void up(int x)

 {

     if (x==||d[s[x>>]]<=d[s[x]]) return;

     swap(s[x],s[x>>]);

     swap(p[s[x]],p[s[x>>]]);

     up(x>>);

 }

 void dijkstra()

 {

     int i,x,k;

     t=s[]=;

     for (i=;i<=n;i++) d[i]=oo;

     while (t)

     {

         x=s[];

         s[]=s[t--];

         p[s[]]=;

         p[x]=-;

         down();

         for (i=first[x];i;i=next[i])

         {

             k=v[i];

             if (p[k]==-) continue;

             if (!p[k])

             {

                 s[++t]=k;

                 p[k]=t;

             }

             if (d[k]>d[x]+w[i])

             {

                 d[k]=d[x]+w[i];

                 up(p[k]);

             }

         }

     }

 }

巴特西

单源最短路模板_SPFA_Dijkstra（堆优化）_C++

最新文章

热门文章