poj 3463 最短路与次短路&&统计个数

时间：2023-01-01 23:06:39

题意：求最短路和比最短路长度多1的次短路的个数

本来想图(有)方(模)便(版)用spfa的，结果妹纸要我看看dijkstra怎么解....

写了三遍orz

Ver1.0：堆优化+邻接表，WA

 //不能用堆优化+邻接表，因为需要处理dis[i][0]和dis[i][1]两套，如果都挤到一个堆里就乱套了

 #include <iostream>

 #include <cstdio>

 #include <queue>

 #include <cstring>

 #include <vector>

 using namespace std;

 const int Ni = ;

 const int INF = <<;

 struct node

 {                   //eg[i].x  eg[i].d    i:start  x:end   d:distance

     int x,d;

     node(){}

     node(int a,int b){x=a;d=b;}

     bool operator < (const node & a) const      //用于优先队列, 取距离原点最近的点

     {

         if(d==a.d) return x<a.x;

         else return d > a.d;

     }

 };

 vector<node> eg[Ni];

 int dis[Ni][],cnt[Ni][],n,T;

 void Dijkstra(int s)    //1.比最短路短2.等于最短路3.长于最短路但短于次短路4.等于次短路

 {

     memset(dis,,sizeof(dis));

     memset(cnt,,sizeof(cnt));

     int i;

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

     {

         dis[i][]=INF;

         dis[i][]=INF;

     }

     dis[s][]=;

     dis[s][]=;

     priority_queue<node> q;         //q：优先队列，用来取离原点最近的顶点

     q.push(node(s,dis[s][]));      //初始只有一个原点自己

     while(!q.empty())

     {

         node x=q.top();q.pop();

         for(i=;i<eg[x.x].size();i++)

         {

             node y=eg[x.x][i];

             if(dis[y.x][]>x.d+y.d)       //

             {

                 cnt[y.x][]=;

                 cnt[y.x][]=;

                 dis[y.x][]=dis[y.x][];

                 dis[y.x][]=x.d+y.d;

                 q.push(node(y.x,dis[y.x][]));

             }

             else if (dis[y.x][]==x.d+y.d)      //

             {

                 cnt[y.x][]++;

             }

             else if ((dis[y.x][]<x.d+y.d)&&(x.d+y.d<dis[y.x][]))      //

             {

                 cnt[y.x][]=;

                 dis[y.x][]=x.d+y.d;

             }

             else if (x.d+y.d==dis[y.x][])      //

             {

                 cnt[y.x][]++;

             }

         }

     }

 }

 void debug()

 {

     cout<<"Debug only"<<endl;

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

         printf("%d - %d %d - %d %d\n",i,dis[i][],cnt[i][],dis[i][],cnt[i][]);

     cout<<ans1<<"    "<<ans2<<endl;

 }

 int main()

 {

     scanf("%d",&T);

     while (T--)

     {

         int a,b,d,m,k,st;

         scanf("%d%d",&n,&m);

         for(int i=;i<=n;i++) eg[i].clear();

         while(m--)

         {

             scanf("%d%d%d",&a,&b,&d);

             eg[a].push_back(node(b,d));

         }

         scanf("%d %d",&k,&st);

         Dijkstra(k);

         debug1();

         int t1=dis[st][],t2=dis[st][],ans1=cnt[st][],ans2;

         if (t2-t1==)

             ans2=cnt[st][];

         else ans2=;

         printf("%d\n",ans1+ans2);

     }

     return ;

 }

Ver2.0：邻接矩阵，WA

 //不能用邻接矩阵，因为会有重边

 #include <iostream>

 #include <cstring>

 using namespace std;

 #define MAXINT 9999999

 int minx,minj,x,y,t,k,n,m,tmp,st,flag;

 int v[][],d[][],cnt[][],a[][];

 int main()

 {

     int T;

     cin>>T;

     while (T--)

     {

         cin>>n>>m;

         memset(a,,sizeof(a));

         memset(d,MAXINT,sizeof(d));

         memset(v,,sizeof(v));

         memset(cnt,,sizeof(cnt));

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

         {

             cin>>x>>y>>t;

             a[x][y]=t;

         }

         cin>>k>>st;

         d[k][]=;  //d[k][2]=0;

         cnt[k][]=;   // cnt[k][2]=1;

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

         {

             minx=MAXINT;

             for (int j=;j<=n;j++)

             {

                 if ((v[j][]==)&&(d[j][]<minx))

                 {

                     minx=d[j][];

                     minj=j;

                     flag=;

                 }

                 if ((v[j][]==)&&(d[j][]<minx))

                 {

                     minx=d[j][];

                     minj=j;

                     flag=;

                 }

             }

             v[minj][flag]=;

             for (int j=;j<=n;j++)

                // if ((v[j][1]==0)&&(a[minj][j]>0))

                if (a[minj][j]>)

             {

                 tmp=minx+a[minj][j];

                 if (tmp<d[j][])

                 {

                     d[j][]=d[j][];

                     d[j][]=tmp;

                     cnt[j][]=cnt[j][];

                     cnt[j][]=cnt[minj][flag];

                 }

                 else if (tmp==d[j][])

                 {

                     cnt[j][]+=cnt[minj][flag];

                 }

                 else if (tmp<d[j][])

                 {

                     d[j][]=tmp;

                     cnt[j][]=cnt[minj][flag];

                 }

                 else if (tmp==d[j][])

                 {

                     cnt[j][]+=cnt[minj][flag];

                 }

             }

     }

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

         cout<<d[i][]<<" "<<cnt[i][]<<" = "<<d[i][]<<" "<<cnt[i][]<<endl;

     cout<<endl;

     int t1=d[st][],t2=d[st][],ans1=cnt[st][],ans2;

     if (t2==t1+) ans2=cnt[st][]; else ans2=;

     cout<<ans1+ans2<<endl;

     }

     return ;

 }

Ver3.0：朴素n^2算法+邻接表  AC

 #include <stdio.h>

 #include <string.h>

 #define INF 999999

 struct node

 {

     int to,dat;

 }edge[][];

 int cnt[][],d[][],vis[][];

 int x,y,z,n,m,T,st,ed;

 void insert_node(int x,int y,int z)

 {

     edge[x][].dat++;

     int tmp=edge[x][].dat;

     edge[x][tmp].to=y;

     edge[x][tmp].dat=z;

 }

 void dijkstra()

 {

     memset(vis,,sizeof(vis));

     memset(d,INF,sizeof(d));

     memset(cnt,,sizeof(cnt));

     d[st][]=;

     cnt[st][]=;

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

     {

         int minj,flag,minx=INF;

         for (int j=;j<=n;j++)

             if ((vis[j][]==)&&(d[j][]<minx))

             {

                 minx=d[j][];

                 minj=j;

                 flag=;

             }

             else if ((vis[j][]==)&&(d[j][]<minx))

             {

                 minx=d[j][];

                 minj=j;

                 flag=;

             }

         vis[minj][flag]=;

         int tmp=edge[minj][].dat;

         for (int j=;j<=tmp;j++)

         {

             int yy=edge[minj][j].to;

             int zz=edge[minj][j].dat;

             //if (vis[yy][flag]==0)

             //{

                 int tm=minx+zz;

                 if (tm<d[yy][])

                 {

                     d[yy][]=d[yy][];

                     cnt[yy][]=cnt[yy][];

                     d[yy][]=tm;

                     cnt[yy][]=cnt[minj][flag];

                 }

                 else if (tm==d[yy][])

                 {

                     cnt[yy][]+=cnt[minj][flag];

                 }

                 else if (tm<d[yy][])

                 {

                     d[yy][]=tm;

                     cnt[yy][]=cnt[minj][flag];

                 }

                 else if (tm==d[yy][])

                 {

                     cnt[yy][]+=cnt[minj][flag];

                 }

             //}

         }

     }

 }

 int main()

 {

 //    freopen("in.txt","r",stdin);

     scanf("%d",&T);

     while (T--)

     {

         memset(edge,,sizeof(edge));

         scanf("%d %d",&n,&m);

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

         {

             scanf("%d %d %d",&x,&y,&z);

             insert_node(x,y,z);

         }

         scanf("%d %d",&st,&ed);

 /*

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

             for (int j=1;j<=edge[i][0].dat;j++)

                 printf("Debug: %d -> %d = %d\n",i,edge[i][j].to,edge[i][j].dat);

 */

         dijkstra();

         int tx,ty,ans2,ans1;

         tx=d[ed][];    ty=d[ed][];

         ans1=cnt[ed][];

         if (ty-tx==)   ans2=cnt[ed][];

             else ans2=;

 //        printf("%Debug: %d %d %d %d\n",tx,ty,ans1,ans2);

         printf("%d\n",ans1+ans2);

     }

     return ;

 }

邻接表很少用到都不大会写了>_<

dij松弛的条件改变下，有四种情况
1.比最短路短2.等于最短路3.长与最短路但短于次短路4.等于次短路

d[i][0]记最短路， d[i][1]记次短路

注意这里：

int tm=minx+zz;

if (tm<d[yy][])

{

    d[yy][]=d[yy][];

    cnt[yy][]=cnt[yy][];

    d[yy][]=tm;

    cnt[yy][]=cnt[minj][flag];

}

else if (tm==d[yy][])

{

    cnt[yy][]+=cnt[minj][flag];

    //因为松弛操作是从minj点开始的

    //（d[minj]+a[minj,j]<d[j]）

    //所以记录cnt的时候要+=cnt[minj][flag]

    //一开始以为直接+1就行，WA了

    //前面的cnt[yy][0]=cnt[minj][flag]同理

}

else if (tm<d[yy][])

{

    d[yy][]=tm;

    cnt[yy][]=cnt[minj][flag];

}

else if (tm==d[yy][])

{

    cnt[yy][]+=cnt[minj][flag];

}

Reference：

http://blog.csdn.net/wmn_wmn/article/details/7376707

http://www.cnblogs.com/Missa/archive/2012/08/31/2665244.html

相关文章