最短路计数—

题目：

　　给出一个N个顶点M条边的无向无权图，顶点编号为1−N。问从顶点1开始，到其他每个点的最短路有几条。

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　——传送门

受到题解的启发，用 Dijkstra A掉（手工代码）

思路：

　　1.无向无权图，建图的时候别忘记建来回的有向边

　　2.无权，那么边长建成1就好了

　　3.最短路采用 Dijkstra（堆优化）来做，计数操作改装进去，tot[1]=1;用 Dijkstra 更新边长的时候如果大于号（具体见代码）就覆盖，相等的话就加上。

AC代码：

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<string>

#include<iostream>

#include<algorithm>

#include<queue>

#include<stack>

#include<deque>

#include<set>

#include<map>

#include<vector>

#include<fstream>

using namespace std;

#define maxn 2000005

#define mod 100003

int head[maxn],vis[maxn],d[maxn],tot[maxn];

int cnt=,n,m,s;

priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;

struct hh

{

    int nex,to;

}t[maxn<<];

inline void add(int nex,int to)

{

    t[++cnt].nex=head[nex];

    t[cnt].to=to;

    head[nex]=cnt;

}

inline int read()

{

    char kr=;

    char ls;

    for(;ls>''||ls<'';kr=ls,ls=getchar());

    int xs=;

    for(;ls>=''&&ls<='';ls=getchar())

    {

        xs=xs*+ls-;

    }

    if(kr=='-') xs=-xs;

    return xs;

}

inline void dijkstra()

{

    memset(d,0x3f,sizeof(d));

    memset(tot,,sizeof(tot));

    memset(vis,,sizeof(vis));

    q.push(make_pair(,));

    d[]=;

    vis[]=;

    tot[]=;

    while(!q.empty())

    {

        int u=q.top().second;

        q.pop();

        vis[u]=;

        for(int v=head[u];v;v=t[v].nex)

        {

            if(d[t[v].to]>d[u]+)

            {

                d[t[v].to]=d[u]+;

                tot[t[v].to]=tot[u];

                if(!vis[v])

                {

                    q.push(make_pair(d[t[v].to],t[v].to));

                    vis[v]=;

                }

                continue;

            }

            else if(d[t[v].to]==d[u]+)

            {

                tot[t[v].to]+=tot[u];//tot记录的是点上的数，不是边上。（查了好久）

                tot[t[v].to]%=mod;

                continue;

            }//关键是这两个 if 语句，其它的跟单源最短路没什么区别

        }

    }

}

int main()

{

    n=read();m=read();

    int x,y;

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

    {

        x=read();y=read();

        add(x,y);

        add(y,x);

    }

    dijkstra();

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

    {

        printf("%d\n",tot[i]);

    }

return ;

}

巴特西

最短路计数——Dijkstra

题目：

思路：

AC代码：

最新文章

热门文章