A - Changing Train Optimization
問題文
Aliceの住む国には $1$ から $N$ の番号が振られた $N$ 個の駅と $1$ から $M$ の番号が振られた $M$ 種類の路線が存在します。
$i$ 番目の路線には $k_i$ 個の停車駅があり、駅 $s_{i,1}$ と駅 $s_{i, 2}$ 、駅 $s_{i,2}$ と駅 $s_{i,3}$ 、 $\cdots$、駅 $s_{i,k_i - 1}$ と駅 $s_{i,k_i}$ をそれぞれ相互に結んでいます。
Aliceは今駅 $1$ にいて、Aliceの大学の最寄り駅である駅 $N$ に向かおうとしています。
Aliceが駅 $1$ から駅 $N$ に辿り着くまでに必要な乗り換え回数の最小値を求めてください。ただし、今日はあまりにも暑いため、任意の $2$ 駅間はいくつかの路線を用いてのみ移動することとします。
ただし、 $3$ 個の駅 $a, b, c$ に対して路線 $i$ を用いて駅 $a$ から駅 $b$ に移動し、 $i \neq j$ を満たす路線 $j$ を用いて駅 $b$ から駅 $c$ に移動したとき、かつこの場合に限り乗り換えたとみなします。また、駅 $1$ と駅 $N$ はいくつかの路線を辿ることで必ず移動することができることが保証されています。
制約
Final (65点)
- $2 \leq N \leq 1500$
- $1 \leq M \leq 1500$
- $2 \leq k_i \leq N$
- $\sum k_i \leq 8 \times 10^5$
- $1 \leq s_{i,j} \leq N$
- $i \neq j$ ならば $s_{p,i} \neq s_{p,j}$
- 駅 $1$ から駅 $N$ へ必ず移動することができる。
- 入力はすべて整数である。
Hard (25点)
- Finalの制約に以下の制約を追加
- $1 \leq M \leq 30$
Normal (30点)
- Finalの制約に以下の制約を追加
- $1 \leq M \leq 10$
Easy (70点)
- Finalの制約に以下の制約を追加
- $2 \le M \le 10$
- 各 $i$ について、 $1 \le j \le k_i$ ならば $s_{i,j} = s_{i,1} + j - 1$
Beginning (10点)
- Finalの制約に以下の制約を追加
- $M = 2$
- 各 $i$ について、 $1 \le j \le k_i$ ならば $s_{i,j} = s_{i,1} + j - 1$
入力
$N\ \ M$
$k_1\ \ s_{1,1}\ \ s_{1,2}\ \ \cdots\ \ s_{1,k_1}$
$k_2\ \ s_{2,1}\ \ s_{2,2}\ \ \cdots\ \ s_{2,k_2}$
$\ \vdots$
$k_M\ \ s_{M,1}\ \ s_{M,2}\ \ \cdots\ \ s_{M,k_M}$
出力
Aliceが駅 $1$ から駅 $N$ まで移動するのに必要な最小の乗り換え回数を出力し、最後に改行してください。
4 2
3 1 2 3
3 2 3 4
1
例えば、 $1$ 番目の路線で駅 $1$ から駅 $3$ まで移動し、 $2$ 番目の路線で駅 $3$ から駅 $4$ に移動する方法が考えられ、このとき乗り換え回数は $1$ 回です。
また、 $1$ 回も乗り換えをせずに駅 $1$ から駅 $4$ まで移動することはできないので、答えは $1$ となります。
入力例1はBeginning, Easy, Normal, Hard, Finalの制約を満たします。
10 4
4 1 2 3 4
6 3 4 5 6 7 8
6 5 6 7 8 9 10
6 2 3 4 5 6 7
2
例えば、 $1$ 番目の路線で駅 $2$ に移動し、 $4$ 番目の路線で駅 $7$ に移動し、 $3$ 番目の路線で駅 $10$ に移動する方法が考えられ、このとき乗り換え回数は $2$ 回です。
また、乗り換え回数を $1$ 回以下にすることはできないので、答えは $2$ となります。
入力例2はEasy, Normal, Hard, Finalの制約を満たします。
10 6
2 2 1
4 4 6 5 7
3 10 9 3
2 8 2
5 10 8 2 1 9
3 2 4 10
0
$5$ 番目の路線を使うことで、 $1$ 回も乗り換えを行うことなく駅 $10$ に移動することができます。
入力例3はNormal, Hard, Finalの制約を満たします。