AT_arc061_c [ARC061E] すぬけ君の地下鉄旅行

[problemUrl]: https://atcoder.jp/contests/arc061/tasks/arc061_c すぬけ君の住んでいる街には地下鉄が走っています。駅は全部で $ N $ 個あり、路線は全部で $ M $ 本あります。 駅には $ 1 $ から $ N $ までの整数が付けられています。また、それぞれの路線はある $ 1 $ つの会社によって運営されており、 それぞれの会社には会社をあらわす整数がつけられています。 $ i $ 番目 ( $ 1\ \leq\ i\ \leq\ M $ ) の路線は、駅 $ p_i $ と 駅 $ q_i $ を相互に結んでいます。途中に他の駅はありません。 また、この路線は会社 $ c_i $ によって運営されています。 同じ駅を通る路線が複数あるときは、その駅で乗り換えることができます。 それぞれの会社について、同じ会社の路線を使い続ける限り料金は $ 1 $ ですが、別の会社の路線に乗り換えるたびに新たに料金が $ 1 $ かかります。 ある会社を利用し、別の会社を利用してからまた最初の会社を利用する場合でも、再び料金を払う必要があります。 すぬけ君は、駅 $ 1 $ を出発し、地下鉄を利用して駅 $ N $ に行きたいです。移動にかかる料金の最小値を求めてください。

N/A

N/A

### 制約 - $ 2\ \leq\ N\ \leq\ 10^5 $ - $ 0\ \leq\ M\ \leq\ 2×10^5 $ - $ 1\ \leq\ p_i\ \leq\ N $ $ (1\ \leq\ i\ \leq\ M) $ - $ 1\ \leq\ q_i\ \leq\ N $ $ (1\ \leq\ i\ \leq\ M) $ - $ 1\ \leq\ c_i\ \leq\ 10^6 $ $ (1\ \leq\ i\ \leq\ M) $ - $ p_i\ \neq\ q_i $ $ (1\ \leq\ i\ \leq\ M) $ ### Sample Explanation 1 $ 1 $ → $ 2 $ → $ 3 $ と会社 $ 1 $ の路線を使って移動することができ、この場合必要なコストは $ 1 $ です。 ### Sample Explanation 2 $ 1 $ → $ 3 $ → $ 2 $ → $ 5 $ → $ 6 $ と会社 $ 1 $ の路線を利用し、その後 $ 6 $ → $ 7 $ → $ 8 $ と会社 $ 5 $ の路線を利用することで、コスト $ 2 $ で目的地に到達できます。