最短路和次短路条数

心已赠人 2022-07-11 13:14 198阅读 0赞

**问题描述：**

给你一张无向图或有向图，要你求任意两点的最短路条数或次短路条数

**算法描述**：

**1，最短路：**

对于最短路条数，我们很容易想到的是加法原则，我们可以在用dij求最短路的时候，

当dis\[j\]=dis\[to\]+mp\[to\]\[j\]时我们知道j点此时有两条不同的路径相同的路径经过，所以

我们可以用个数组cnt\[j\]表示经过j点的最短路条数，所以我们可以得到此时cnt\[j\]+=cnt\[to\]

而当大于时cnt\[j\]=cnt\[to\]

** 2，次短路：**

对于次短路，我们可以采取和最短路一样的策略，也是加法原则，我们可以用个二维的

数组来分别记录最短路和次短路，即dis\[\]\[2\],cnt\[\]\[2\],而我们知道次短路是要比最短路长的，所以

当更新最短路时我们知道更新前的最短路要比更新后的最短路要长，所以我们不妨让此时的

次短路等于更新前的最短路，而当最短路不能更新即，dis\[j\]<dis\[to\]+mp\[to\]\[j\]时，我们可以让

此时的次短路来和后面的比较，如果比后面的大，说明此时次短路应该更新，如果等于说明该

点次短路条数增加！

**算法例子：**

**1，HDU-3191 ：**求次短路长度和条数，但这题有个坑就是边权值可以为0，所以如果用优先队列的话会出错，普通的就行。

AC代码：

#include<algorithm>
    #include<cstdio>
    #include<queue>
    using namespace std;
    const int maxn = 1e3+10;
    const int inf = 1e9;
    
    class Edge{
    public:
        int v,w,nex;
    };
    
    class num_Shortpath{
    public:
        int n,m,e;
        int dis[maxn][2], cnt[maxn][2],vis[maxn][2],hed[maxn];
        Edge edge[maxn*maxn];
    
        queue<pair<int,int> >q;
    
        void add(int u,int v,int w){
            edge[e].v=v,edge[e].w=w,edge[e].nex=hed[u],hed[u]=e++;
        }
    
        void init(){
            int s0,e0;
            while( ~scanf("%d%d%d%d",&n,&m,&s0,&e0)){
                s0++,e0++;
                for(int i=1;i<=n;i++)hed[i]=-1,vis[i][0]=vis[i][1]=0;e=1;
                for(int i=0;i<m;i++){
                     int u,v,w;scanf("%d%d%d",&u,&v,&w);
                     u++,v++;
                     add(u,v,w);
                }
                spfa(s0);
                printf("%d %d\n",dis[e0][1],cnt[e0][1]);
            }
        }
    
        void spfa(int u){
            for(int i=1;i<=n;i++){
                dis[i][0]=inf,cnt[i][1]=0;
                dis[i][1]=inf,cnt[i][1]=0;
                vis[i][0]=vis[i][1]=0;
            }
            dis[u][0]=0,cnt[u][0]=1;
            q.push(make_pair(u,0));
            while(!q.empty()){
                int to = q.front().first,flag = q.front().second;q.pop();
                if(vis[to][flag])continue;
                vis[to][flag]=1;
                for(int i=hed[to];~i;i=edge[i].nex){
                    int j = edge[i].v;
                    int tmp = dis[to][flag]+edge[i].w;
                    if(dis[j][0]>tmp){
                        if(dis[j][0]!=inf){
                        dis[j][1]=dis[j][0];
                        cnt[j][1]=cnt[j][0];
                        q.push(make_pair(j,1));
                        }
                        dis[j][0]=tmp;
                        cnt[j][0]=cnt[to][flag];
                        q.push(make_pair(j,0));
                    }
                    else if(dis[j][0]==tmp){
                        cnt[j][0]+=cnt[to][flag];
                    }
                    else if(dis[j][1]>tmp){
                        dis[j][1]=tmp;
                        cnt[j][1]=cnt[to][flag];
                        q.push(make_pair(j,1));
                    }
                    else if(dis[j][1]==tmp){
                        cnt[j][1]+=cnt[to][flag];
                    }
                }
            }
        }
    
    }ns;
    
    int main()
    {
        ns.init();
        return 0;
    }

**2，HDU1688**\-分别求最短路条数和次短路条数，要求差值为1，这个就要用优先队列才可以过

AC代码：

#include<algorithm>
    #include<cstdio>
    #include<queue>
    using namespace std;
    const int maxn = 1e3+10;
    const int inf = 1e9;
    int dis[maxn][2];
    class Edge{
    public:
        int v,w,nex;
    };
    
    class Nod{
    public:
        int first,second;
        Nod(int a,int b){
            first = a,second=b;
        }
        bool operator <(const Nod &t)const{
            return dis[first][second]>dis[t.first][t.second];
        }
    };
    
    class num_Shortpath{
    public:
        int n,m,e;
        int cnt[maxn][2],vis[maxn][2],hed[maxn];
        Edge edge[maxn*maxn];
    
        priority_queue<Nod>q;
    
        void add(int u,int v,int w){
            edge[e].v=v,edge[e].w=w,edge[e].nex=hed[u],hed[u]=e++;
        }
    
        void init(){
            int t;scanf("%d",&t);
            while(t--){
                scanf("%d%d",&n,&m);
                for(int i=1;i<=n;i++)hed[i]=-1,vis[i][0]=vis[i][1]=0;e=1;
                for(int i=0;i<m;i++){
                     int u,v,w;scanf("%d%d%d",&u,&v,&w);
                     add(u,v,w);
                }
                int u,v;scanf("%d%d",&u,&v);
                spfa(u);
                if(dis[v][0]==dis[v][1]-1)
                printf("%d\n",cnt[v][0]+cnt[v][1]);
                else printf("%d\n",cnt[v][0]);
            }
        }
    
        void spfa(int u){
            for(int i=1;i<=n;i++){
                dis[i][0]=inf,cnt[i][1]=0;
                dis[i][1]=inf,cnt[i][1]=0;
                vis[i][0]=vis[i][1]=0;
            }
            dis[u][0]=0,cnt[u][0]=1;
            q.push(Nod(u,0));
            while(!q.empty()){
                int to = q.top().first,flag = q.top().second;q.pop();
                if(vis[to][flag])continue;
                vis[to][flag]=1;
                for(int i=hed[to];~i;i=edge[i].nex){
                    int j = edge[i].v;
                    int tmp = dis[to][flag]+edge[i].w;
                    if(dis[j][0]>tmp){
                        if(dis[j][0]!=inf){
                        dis[j][1]=dis[j][0];
                        cnt[j][1]=cnt[j][0];
                        q.push(Nod(j,1));
                        }
                        dis[j][0]=tmp;
                        cnt[j][0]=cnt[to][flag];
                        q.push(Nod(j,0));
                    }
                    else if(dis[j][0]==tmp){
                        cnt[j][0]+=cnt[to][flag];
                    }
                    else if(dis[j][1]>tmp){
                        dis[j][1]=tmp;
                        cnt[j][1]=cnt[to][flag];
                        q.push(Nod(j,1));
                    }
                    else if(dis[j][1]==tmp){
                        cnt[j][1]+=cnt[to][flag];
                    }
                }
            }
        }
    
    }ns;
    
    int main()
    {
        ns.init();
        return 0;
    }