题目描述

给出一个 N 个顶点 M 条边的无向无权图，顶点编号为 1 到 N。

问从顶点 1 开始，到其他每个点的最短路有几条。

输入格式
第一行包含 2 个正整数 N,M，为图的顶点数与边数。

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

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

如果无法到达顶点 i 则输出 0。

数据范围
1≤N≤105,
1≤M≤2×105

样例

输入样例

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

输出样例

1
1
1
2
4

算法1

Dijkstra

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int , int>PII;

const int N = 100010 , M = 400010 , MOD = 100003;

int n , m;
int h[N] , e[M] , ne[M] , idx;
int dis[N] , cnt[N];
bool st[N];

void add(int a , int b)
{
    e[idx] = b , ne[idx] = h[a] , h[a] = idx ++ ;
}

void dijkstra()
{
    memset(dis , 0x3f , sizeof dis);
    dis[1] = 0;
    cnt[1] = 1;

    priority_queue<PII , vector<PII> , greater<PII>> heap;
    heap.push({0 , 1});

    while(!heap.empty())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second , distance = t.first;
        if(st[ver]) continue;
        st[ver] = true;

        for(int i = h[ver] ; i != -1 ; i = ne[i])
        {
            int j = e[i];
            if(dis[j] > distance + 1)
            {
                dis[j] = distance + 1;
                cnt[j] = cnt[ver];
                heap.push({dis[j] , j});
            }
            else if(dis[j] == distance + 1) cnt[j] = (cnt[j] + cnt[ver]) % MOD;
        }
    }
}

int main()
{
    cin >> n >> m;

    memset(h , -1 , sizeof h);

    while(m -- )
    {
        int a , b;
        cin >> a >> b;
        add(a , b) , add(b , a);
    }

    dijkstra();

    for(int i = 1 ; i <= n ; i ++ ) cout << cnt[i] << endl;

    return 0;
}

算法2

BFS

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int , int>PII;

const int N = 100010 , M = 400010 , MOD = 100003;

int n , m;
int h[N] , e[M] , ne[M] , idx;
int dis[N] , cnt[N];

void add(int a , int b)
{
    e[idx] = b , ne[idx] = h[a] , h[a] = idx ++ ;
}

void bfs()
{
    memset(dis , 0x3f , sizeof dis);
    dis[1] = 0;
    cnt[1] = 1;

    queue<int>q;
    q.push(1);

    while(!q.empty())
    {
        auto t = q.front();
        q.pop();

        for(int i = h[t] ; i != -1 ; i = ne[i])
        {
            int j = e[i];
            if(dis[j] > dis[t] + 1)
            {
                dis[j] = dis[t] + 1;
                cnt[j] = cnt[t];
                q.push(j);
            }
            else if(dis[j] == dis[t] + 1) cnt[j] = (cnt[j] + cnt[t]) % MOD;
        }
    }
}

int main()
{
    cin >> n >> m;

    memset(h , -1 , sizeof h);

    while(m -- )
    {
        int a , b;
        cin >> a >> b;
        add(a , b) , add(b , a);
    }

    bfs();

    for(int i = 1 ; i <= n ; i ++ ) cout << cnt[i] << endl;

    return 0;
}