cpp
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MOD = 100003; // 题目要求的模数

int main() {
    int N, M;
    cin >> N >> M; // 读取顶点数 N 和边数 M

    vector<vector<int>> graph(N + 1); // 用邻接表存储图
    vector<int> dist(N + 1, -1);  // 到达每个顶点的距离，-1 表示尚未访问
    vector<int> ways(N + 1, 0);   // 从顶点1到各个顶点的最短路的数量

    for (int i = 0; i < M; ++i) {
        int x, y;
        cin >> x >> y;
        graph[x].push_back(y); // 无向图，连接两个顶点
        graph[y].push_back(x); // 同样需要连接回来
    }

    queue<int> q; // 使用队列进行BFS
    q.push(1); // 从顶点1开始
    dist[1] = 0; // 顶点1到达自身的距离为0
    ways[1] = 1; // 从顶点1到达自身的最短路数量为1

    while (!q.empty()) {
        int current = q.front(); // 取出队列中的当前顶点
        q.pop();

        for (int neighbor : graph[current]) {
            if (dist[neighbor] == -1) {
                dist[neighbor] = dist[current] + 1; // 计算到达邻居的距离
                ways[neighbor] = ways[current]; // 以当前顶点的最短路数量初始化邻居的数量
                q.push(neighbor); // 将邻居加入队列，继续BFS
            } else if (dist[neighbor] == dist[current] + 1) {
                ways[neighbor] = (ways[neighbor] + ways[current]) % MOD; // 若距离相等，累加最短路数量，注意取模
            }
        }
    }



    for (int i = 1; i <= N; ++i) {
        if (dist[i] == -1) {
            cout << 0 << endl; // 无法到达的顶点最短路数量为0
        } else {
            cout << ways[i] << endl; // 输出到各个顶点的最短路数量
        }
    }

    return 0;
}

spfa解答

cpp
#include <bits/stdc++.h>
using namespace std;

const int MOD = 100003;
const int MAXN = 1000007;
const int INF = 0x3f3f3f3f;

vector<pair<int, int>> edges[MAXN];
int dist[MAXN], ways[MAXN];
bool in_queue[MAXN];
queue<int> q;

void spfa(int start) {
    memset(dist, INF, sizeof(dist));
    memset(ways, 0, sizeof(ways));
    memset(in_queue, false, sizeof(in_queue));

    dist[start] = 0;
    ways[start] = 1;
    in_queue[start] = true;
    q.push(start);

    while (!q.empty()) {
        int current = q.front();
        q.pop();
        in_queue[current] = false;

        for (auto edge : edges[current]) {
            int neighbor = edge.first;
            int weight = edge.second;

            if (dist[neighbor] > dist[current] + 1) {
                dist[neighbor] = dist[current] + 1;
                ways[neighbor] = ways[current];
                
                if (!in_queue[neighbor]) {
                    q.push(neighbor);
                    in_queue[neighbor] = true;
                }
            } else if (dist[neighbor] == dist[current] + 1) {
                ways[neighbor] += ways[current];
                ways[neighbor] %= MOD;
            }
        }
    }
}

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

    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        edges[x].push_back({y, 1});
        edges[y].push_back({x, 1});
    }

    spfa(1);

    for (int i = 1; i <= n; i++) {
        if (dist[i] == INF) {
            cout << 0 << endl;
        } else {
            cout << ways[i] << endl;
        }
    }

    return 0;
}