题目：https://www.luogu.org/problem/P1144

题目描述

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

输入格式

第一行包含22个正整数$N,M$，为图的顶点数与边数。

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

输出格式

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

题解

我们开一个$ans$数组，记录$１$号到点到当前节点的路径个数。

所以，我们只需多加下面的代码即可：

if (dis[v] == dis[u] + 1)
    ans[v] = (ans[v] + ans[u]) % 100003;

Code

#include <algorithm>
#include <iostream>
#include <queue>
#define maxn 2000002
#define endl '\n'
#define pairs pair<int, int>
#define mod % 100003
using namespace std;

struct node
{
    int to, next;
} edge[maxn << 1];

int n, m;
int head[maxn], num;
int vis[maxn], dis[maxn];
long long ans[maxn];

inline void add_edge (int from, int to)
{
    edge[++num].next = head[from];
    edge[num].to = to;
    head[from] = num;
}

inline void dijkstra (int x)
{
    ans[x] = 1;
    for (register int i = 1; i <= n; i++) dis[i] = 2147483647;
    priority_queue<pairs> q;
    dis[x] = 0;
    q.push (make_pair (0, 1));
    while (!q.empty ())
    {
        int u = q.top ().second;
        q.pop ();
        if (vis[u]) continue;
        vis[u] = 1;
        for (register int i = head[u]; i; i = edge[i].next)
        {
            int v = edge[i].to;
            if (dis[v] > dis[u] + 1)
            {
                dis[v] = dis[u] + 1;
                q.push (make_pair (-dis[v], v));
            }
            if (dis[v] == dis[u] + 1) ans[v] = (ans[v] + ans[u])mod;
        }
    }
}

int main ()
{
    ios::sync_with_stdio (false);
    cin.tie (0);
    cout.tie (0);

    cin >> n >> m;
    for (register int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        add_edge (x, y);
        add_edge (y, x);
    }

    dijkstra (1);

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

    return 0;
}