[ARC061E] すぬけ君の地下鉄旅行
题意翻译
## 题目描述
Snuke的城镇有地铁行驶,地铁线路图包括 $N$ 个站点和 $M$ 个地铁线。站点被从 $1$ 到 $N$ 的整数所标记,每条线路被一个公司所拥有,并且每个公司用彼此不同的整数来表示。
第 $i$ 条线路( $1≤i≤M$ )是直接连接 $p_i$ 与 $q_i$ 的双向铁路,中间不存在其他站点,且这条铁路由 $c_i$ 公司所拥有。
如果乘客只乘坐同一公司的铁路,他只需要花费一元,但如果更换其他公司的铁路需要再花一元。当然,如果你要再换回原来的公司,你还是要花一元。
Snuke在1号站的位置出发,他想通过地铁去第 $N$ 站,请求出最小钱数。如果无法到达第 $N$ 站,输出-1。
## 输入输出格式
### 输入格式
第一行,输入 $N$ , $M$
接下来的 $M$ 行,输入 $p_i$ $q_i$ $c_i$ ,代表 $p_i$ 与 $q_i$ 中间有直接连接的双向边,且这条铁路由 $c_i$ 公司所拥有。
### 输出格式
输出最小钱数(若无法到达,输出-1)
感谢@SaltedHXJ 提供的翻译
题目描述
[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 $ $ M $ $ p_1 $ $ q_1 $ $ c_1 $ : $ p_M $ $ q_M $ $ c_M $
输出格式
移動にかかる料金の最小値を出力せよ。すぬけ君が駅 $ N $ に到達することが不可能な場合には、代わりに `-1` を出力せよ。
输入输出样例
输入样例 #1
3 3
1 2 1
2 3 1
3 1 2
输出样例 #1
1
输入样例 #2
8 11
1 3 1
1 4 2
2 3 1
2 5 1
3 4 3
3 6 3
3 7 3
4 8 4
5 6 1
6 7 5
7 8 5
输出样例 #2
2
输入样例 #3
2 0
输出样例 #3
-1
说明
### 制約
- $ 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 $ で目的地に到達できます。