P1144 Shortest Path Counting

Given an undirected, unweighted graph with $N$ vertices and $M$ edges, where vertices are numbered $1\sim N$. Starting from vertex $1$, determine how many shortest paths there are to every other vertex.

The first line contains $2$ positive integers $N, M$, the number of vertices and edges of the graph. The next $M$ lines each contain $2$ positive integers $x, y$, indicating there is an edge connecting vertex $x$ and vertex $y$. Note that self-loops and multiple edges may exist.

Output $N$ lines. The $i$-th line contains a non-negative integer: the number of different shortest paths from vertex $1$ to vertex $i$. Since the answer can be large, you only need to output $ans \bmod 100003$. If vertex $i$ is unreachable, output $0$.

From $1$ to $5$, there are $4$ shortest paths: $2$ paths $1\to 2\to 4\to 5$ and $2$ paths $1\to 3\to 4\to 5$ (because there are $2$ edges between $4$ and $5$). Constraints: - For $20\%$ of the testdata, $1\le N \le 100$. - For $60\%$ of the testdata, $1\le N \le 10^3$. - For $100\%$ of the testdata, $1\le N \le 10^6$, $1\le M \le 2\times 10^6$. Translated by ChatGPT 5