POJ 2449Remmarguts' Date K短路模板 SPFA+A*

K短路模板，A*+SPFA求K短路。A*中h的求法为在反图中做SPFA，求出到T点的最短路，极为估价函数h（这里不再是估价，而是准确值），然后跑A*，从S点开始（此时为最短路），然后把与S点能达到的点加入堆中，维护堆，再从堆顶取当前g值最小的点(此时为第2短路)，再添加相邻的点放入堆中，依此类推······保证第k次从堆顶取到的点都是第k短路（至于为什么，自己想）其实就是A*算法，这里太啰嗦了

　1 #include<queue>
  2 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int v[],v2[],c[],c2[],s,t,k,duin;

 int n,m,point[],next[],cnt=,point2[],next2[],cnt2=;

 int dist[],vis[],cont[],duig[],duiu[],duif[];

 queue<int>q;

 void insect(int u,int e,int z)

 {cnt++; next[cnt]=point[u]; point[u]=cnt; v[cnt]=e; c[cnt]=z;}

 void insect2(int u,int e,int z)

 {cnt2++; next2[cnt2]=point2[u]; point2[u]=cnt2; v2[cnt2]=e; c2[cnt2]=z;}

 void spfa()

 {    int e,mp; while (!q.empty()) q.pop();

     memset(vis,,sizeof(vis));

     memset(dist,,sizeof(dist));

     dist[t]=; vis[t]=; q.push(t);

     while (!q.empty())

     {

         e=q.front(); q.pop(); vis[e]=;

         for (mp=point2[e];mp!=;mp=next2[mp])

         {

             if (dist[v2[mp]]>dist[e]+c2[mp])

             {

                 dist[v2[mp]]=dist[e]+c2[mp];

                 if (vis[v2[mp]]==)

                 {

                     vis[v2[mp]]=;

                     q.push(v2[mp]);

                 }

             }

         }

     }

 }

 void swap(int &a,int &b){int c=a;a=b;b=c;}

 void popdui()

 {

     duif[]=duif[duin]; duiu[]=duiu[duin]; duig[]=duig[duin];

     duin--;

     int i=;

     while (i<duin)

     {

         if (((duif[i]<duif[i*])||(i*>duin))&&((duif[i]<duif[i*+])||(i*+>duin)))

          return;

         if (i*+<=duin)

          if (duif[i*+]<duif[i*])

          {    swap(duif[i],duif[i*+]);swap(duig[i],duig[i*+]);

              swap(duiu[i],duiu[i*+]);i=i*+;}

          else

          {     swap(duif[i],duif[i*]);swap(duig[i],duig[i*]);

              swap(duiu[i],duiu[i*]);i=i*;}

         else

          {     swap(duif[i],duif[i*]);swap(duig[i],duig[i*]);

              swap(duiu[i],duiu[i*]);i=i*;}

     }

 }

 void puss(int vv,int gg,int ff)

 {

     duin++;

     duiu[duin]=vv;duig[duin]=gg;duif[duin]=ff;

     int i=duin;

     while (i>)

     {

         if (duif[i]<duif[i/])

         {

             swap(duif[i],duif[i/]);

             swap(duiu[i],duiu[i/]);

             swap(duig[i],duig[i/]);

         }

         else return;

         i=i/;

     }

 }

 int astar()

 {

     memset(cont,,sizeof(cont));

     memset(duif,,sizeof(duif));

     memset(duiu,,sizeof(duiu));

     memset(duig,,sizeof(duig));

     if (s==t) k++; cnt=;

     int f,u,now,i; duin=;duif[]=dist[s];duiu[]=s;duig[]=;

     while (duin>)

     {

         f=duif[]; u=duiu[]; now=duig[];

         popdui();

         if (u==t) cnt++;

         if (cnt==k) return now;

         for (i=point[u];i!=;i=next[i])

         {

             puss(v[i],now+c[i],now+c[i]+dist[v[i]]);

         }

     }

     return -;

 }

 int main()

 {

     int i,j,a,b,cc;

     while (scanf("%d %d\n",&n,&m)!=EOF)

     {

         memset(point,,sizeof(point)); memset(point2,,sizeof(point2));

         memset(next,,sizeof(next)); memset(next2,,sizeof(next2));

         memset(v,,sizeof(v)); memset(v2,,sizeof(v2));

         memset(c,,sizeof(c)); memset(c2,,sizeof(c2));

         cnt=; cnt2=;

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

         {

             scanf("%d %d %d\n",&a,&b,&cc);

             insect(a,b,cc); insect2(b,a,cc);

         } scanf("%d %d %d\n",&s,&t,&k);

         spfa();

         printf("%d\n",astar()); break;

     }

     return ;

 }

巴特西

POJ 2449Remmarguts' Date K短路模板 SPFA+A*

最新文章

热门文章