103196: [Atcoder]ABC319 G - Counting Shortest Paths
Description
Score : $575$ points
Problem Statement
We will perform the following operation on a complete undirected graph $G$ with $N$ vertices.
For each $i = 1, 2, \ldots, M$, delete the undirected edge connecting vertices $u_i$ and $v_i$.
Determine if there is a path from vertex $1$ to vertex $N$ in $G$ after the operation. If there is, find the number, modulo $998244353$, of shortest paths from vertex $1$ to vertex $N$.
Here, a shortest path from vertex $1$ to vertex $N$ is a path from vertex $1$ to vertex $N$ that contains the minimum number of edges.
Constraints
- $2 \leq N \leq 2 \times 10^5$
- $0 \leq M \leq \min\lbrace 2 \times 10^5, N(N-1)/2 \rbrace$
- $1 \leq u_i, v_i \leq N$
- $u_i \neq v_i$
- $i \neq j \implies \lbrace u_i, v_i \rbrace \neq \lbrace u_j, v_j \rbrace$
- All input values are integers.
Input
The input is given from Standard Input in the following format:
$N$ $M$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_M$ $v_M$
Output
If there is no path from vertex $1$ to vertex $N$ in $G$ after the operation, print -1
. If there is, print the number, modulo $998244353$, of shortest paths from vertex $1$ to vertex $N$.
Sample Input 1
6 7 4 3 1 3 2 4 1 6 4 6 5 1 6 2
Sample Output 1
3
In $G$ after the operation, the shortest paths from vertex $1$ to vertex $N$ are the following three, each containing three edges.
- vertex $1$ $\rightarrow$ vertex $2$ $\rightarrow$ vertex $3$ $\rightarrow$ vertex $6$
- vertex $1$ $\rightarrow$ vertex $2$ $\rightarrow$ vertex $5$ $\rightarrow$ vertex $6$
- vertex $1$ $\rightarrow$ vertex $4$ $\rightarrow$ vertex $5$ $\rightarrow$ vertex $6$
Sample Input 2
4 6 1 2 1 3 1 4 2 3 2 4 3 4
Sample Output 2
-1
$G$ has no edges after the operation. There is no path from vertex $1$ to vertex $N$, so print -1
.
Input
Output
问题描述
我们将对一个具有$N$个顶点的完全无向图$G$执行以下操作。
对于每个$i=1,2,\ldots,M$,删除连接顶点$u_i$和$v_i$的无向边。
确定操作后图$G$中是否存在从顶点$1$到顶点$N$的路径。如果存在,找到从顶点$1$到顶点$N$的最短路径的数量,模为$998244353$。
这里,从顶点$1$到顶点$N$的最短路径是从顶点$1$到顶点$N$的包含最少边的路径。
约束
- $2 \leq N \leq 2 \times 10^5$
- $0 \leq M \leq \min\lbrace 2 \times 10^5, N(N-1)/2 \rbrace$
- $1 \leq u_i, v_i \leq N$
- $u_i \neq v_i$
- $i \neq j \implies \lbrace u_i, v_i \rbrace \neq \lbrace u_j, v_j \rbrace$
- 所有输入值都是整数。
输入
输入从标准输入以以下格式给出:
$N$ $M$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_M$ $v_M$
输出
如果操作后图$G$中不存在从顶点$1$到顶点$N$的路径,打印-1
。如果存在,打印从顶点$1$到顶点$N$的最短路径的数量,模为$998244353$。
样例输入1
6 7 4 3 1 3 2 4 1 6 4 6 5 1 6 2
样例输出1
3
操作后的图$G$中,从顶点$1$到顶点$N$的最短路径如下三个,每个包含三个边。
- 顶点$1$ $\rightarrow$ 顶点$2$ $\rightarrow$ 顶点$3$ $\rightarrow$ 顶点$6$
- 顶点$1$ $\rightarrow$ 顶点$2$ $\rightarrow$ 顶点$5$ $\rightarrow$ 顶点$6$
- 顶点$1$ $\rightarrow$ 顶点$4$ $\rightarrow$ 顶点$5$ $\rightarrow$ 顶点$6$
样例输入2
4 6 1 2 1 3 1 4 2 3 2 4 3 4
样例输出2
-1
操作后图$G$中没有边。从顶点$1$到顶点$N$没有路径,所以打印-1
。