yowayimono

2023-10-20

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; // 若距离相等，累加最短路数量，注意取模
            }
        }
    }