问题 M: 最短路计数

时间限制: 1 Sec  内存限制: 128 MB
提交: 25  解决: 8
[提交] [状态] [命题人:admin]

题目描述

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

 

输入

第一行包含2个正整数N,M，为图的顶点数与边数。
接下来行，每行两个正整数x,y，表示有一条顶点x连向顶点y的边，请注意可能有自环与重边。

 

输出

输出N行，每行一个非负整数，第i行输出从顶点1到顶点i有多少条不同的最短路，由于答案有可能会很大，你只需要输出 mod 100003
后的结果即可。如果无法到达顶点i则输出0。

 

样例输入

复制样例数据

5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5

样例输出

1
1
1
2
4

 

提示

1到5的最短路有4条，分别为2条1→2→4→5和2条1→3→4→5（由于4→5的边有2条）。
对于100%的数据，1≤N≤100000,0≤M≤200000。

题目思路:我们根据判断最短路的松弛条件去做即可,如果当前dis[e]>dis[u]+w 那么说明曾经没有最短路,现在新的成为最短路.dp[e]=dp[u] 否则如果相等dp[e]+=dp[u] 找出这个方程之后 用spfa 或者djikstra都可以跑

AC:

#include <bits/stdc++.h>
#include <string>
#pragma GCC optimize(2)
typedef long long ll;
typedef unsigned long long ull;
const int mod=998244353;
const int maxn=1e6+5;
const ll INF=10000000000000005;
using namespace std;
ll n,m,p;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll dp[maxn];
ll dis[maxn];
int vis[maxn];
struct node{
    int e,next;
    ll w;
}edge[maxn];
int head[maxn];
ll cnt=0;
void addedge(int u,int v,int w)
{
    edge[cnt]=node{v,head[u],w};
    head[u]=cnt++;
}
struct N{
    int id;
    ll w;
    bool friend operator<(N a,N b)
    {
        return a.w>b.w;
    }
};
void dijstra()
{
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;i++) dis[i]=INF,dp[i]=0;
    dis[1]=0;
    dp[1]=1;
    N s;s.id=1;s.w=0;
    priority_queue<N>q;
    q.push(s);
    while(1)
    {
        if(q.empty()) break;
        N u=q.top();q.pop();
        if(dis[u.id]!=u.w) continue;
        for(int i=head[u.id];~i;i=edge[i].next)
        {
            int e=edge[i].e;
            if(dis[e]>=u.w+edge[i].w)
            {
                if(dis[e]>u.w+edge[i].w)
                {
                    dp[e]=dp[u.id];
                    dis[e]=u.w+edge[i].w;
                    N now;now.id=e;
                    now.w=dis[e];
                    q.push(now);
                }
                else if(dis[e]==u.w+edge[i].w)
                    dp[e]=(dp[e]+dp[u.id])%100003;
            }
        }
    }
    return;
}
int main()
{
    memset(head,-1,sizeof(head));
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;ll z;
        scanf("%d%d",&x,&y);
        addedge(x,y,1);
        addedge(y,x,1);

    }
    dijstra();
    for(int i=1;i<=n;i++)
        printf("%lld\n",dp[i]);
    return 0;
}