Blocked Roads

题目描述

给出一个有向图，包含 $N$ 个顶点和 $M$ 条边。顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。第 $i$ 条边 $(1 \leq i \leq M)$ 从顶点 $s_i$ 指向顶点 $t_i$，且长度为 $1$。 对于每个 $i$ $(1 \leq i \leq M)$，当除了第 $i$ 条边外所有边都可通行时，求从顶点 $1$ 到顶点 $N$ 的最短距离；如果从顶点 $1$ 无法到达顶点 $N$，则输出 $-1$。

输入格式

输入从标准输入按如下格式给出： $N$ $M$ $s_1$ $t_1$ $s_2$ $t_2$ $\vdots$ $s_M$ $t_M$

输出格式

输出 $M$ 行。 第 $i$ 行应当包含当除了第 $i$ 条边外所有边都可通行时，从顶点 $1$ 到顶点 $N$ 的最短距离；如果从顶点 $1$ 无法到达顶点 $N$，则输出 $-1$。

3 3
1 2
1 3
2 3

1
2
1

4 4
1 2
2 3
2 4
3 4

-1
2
3
2

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

1
1
3
1
1
1
1
1
1
1

4 1
1 2

-1

提示

$2 \leq N \leq 400$ $1 \leq M \leq N(N-1)$ $1 \leq s_i,t_i \leq N$ $s_i \neq t_i$ $(s_i,t_i) \neq (s_j,t_j)$ $(i \neq j)$ 输入中的所有数值均为整数。当除了第 $1$ 条边外所有边都可通行时，顶点 $N$ 无法从顶点 $1$ 到达，因此对应行包含 $-1$。

标签: AtCoder|abc218F

来源

AtCoder|abc218F