Number of Shortest paths

题目描述

共和国 AtCoder 有 $N$ 个城市，编号为 $1$ 到 $N$，有 $M$ 条道路，编号为 $1$ 到 $M$。 使用道路 $i$，你可以在一小时内从城市 $A_i$ 到达 $B_i$ 或反向行驶。 有多少条路径可以让你以最快的时间从城市 $1$ 到达城市 $N$？
由于计数可能非常大，请输出对 $(10^9 + 7)$ 取模的结果。

输入格式

输入按以下格式由标准输入提供： $N$ $M$ $A_1$ $B_1$ $\vdots$ $A_M$ $B_M$

输出格式

输出答案。 如果无法从城市 $1$ 到达城市 $N$，则输出 $0$。

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

2

4 3
1 3
2 3
2 4

1

2 0

0

7 8
1 3
1 4
2 3
2 4
2 5
2 6
5 7
6 7

4

提示

$2 \leq N \leq 2\times 10^5$ $0 \leq M \leq 2\times 10^5$ 1 \leq A_i < B_i \leq N 对 $(A_i, B_i)$ 的配对都是不同的。 输入中的所有值均为整数。从城市 $1$ 到城市 $4$ 所需的最短时间是 $2$ 小时，可以由两条路径达到：$1 \to 2 \to 4$ 和 $1 \to 3 \to 4$。
从城市 $1$ 到城市 $4$ 所需的最短时间是 $3$ 小时，可以由一条路径达到：$1 \to 3 \to 2 \to 4$。
无法从城市 $1$ 到达城市 $2$，在这种情况下你应该输出 $0$。

标签: AtCoder|abc211D

来源

AtCoder|abc211D