33OJ
登录 注册

#ABC485E. 彩色路径

彩色路径

彩色路径

题目描述

有 NN 个城市和 MM 条单向道路。第 ii 条道路从城市 UiU_i 通向城市 ViV_i,颜色为 CiC_i。

你希望从城市 11 出发,反复经过道路到达城市 NN。但是,不能连续两次经过颜色相同的道路。

请判断能否从城市 11 到达城市 NN;如果可以,求出最少需要经过多少条道路。

输入格式

输入第一行为两个整数 N,MN,M。

接下来 MM 行,第 ii 行为三个整数 Ui,Vi,CiU_i,V_i,C_i。

输出格式

如果无法从城市 11 到达城市 NN,输出 −1-1;否则输出最少需要经过的道路条数。

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

样例 1 解释

依次经过第 1,2,5,41,2,5,4 条道路即可从城市 11 到达城市 66,颜色依次为 1,2,3,51,2,3,5,没有连续相同的颜色,共经过 44 条道路。

3 5
1 2 1
1 2 1
1 2 2
1 2 2
1 2 3
-1
8 10
1 2 1
2 3 2
2 4 1
3 2 3
4 5 2
4 6 1
5 4 3
6 7 2
6 8 1
7 6 3
10

数据范围

对于所有测试数据,保证:

  • 2≤N≤2×1052 \le N \le 2 \times 10^5;
  • 1≤M≤2×1051 \le M \le 2 \times 10^5;
  • 1≤Ui,Vi≤N1 \le U_i,V_i \le N,Ui≠ViU_i \neq V_i;
  • 1≤Ci≤M1 \le C_i \le M;
  • 所有输入值均为整数。

子任务

本题共 20 个测试点,按测试点计分:

测试点 分值 每个测试点 特殊性质
1∼61 \sim 6 3030 55 N,M≤2000N, M \le 2000
7∼127 \sim 12 N,M≤5×104N, M \le 5 \times 10^4
13∼2013 \sim 20 4040 无特殊限制

每个测试点单独评分,全部测试点的得分之和即为本题得分。